第十五届蓝桥杯省赛 Java A 组 Q1~Q3 题解
Q1 拼正方形
题目链接：
算法分析： 将问题转化为同一单位计算。以 2×2 的方块作为一个单位，将 1×1 的方块换算成 2×2 的方块数。统计 2×2 能拼成多大边长的正方形，最后结果乘以 2。 设总等效 2×2 方块数为 $M = A + B/4$，其中 $A=7385137888721, B=10470245$。 注意：2×2 的方块不能拆成 4 个 1×1 的。 时间复杂度为 $O(M)$。
Java 代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
long A = 7385137888721L;
long B = 10470245L;
long i = 1;
while (true) {
if (i * i > A + B / 4) break;
i++;
}
System.out.println(2 * (i - 1));
}
}
Q2 召唤数学精灵
题目链接：
算法分析： 利用同余定理求解。需满足 $(A(i) - B(i)) % 100 = 0$，即 $A(i) % 100 = B(i) % 100$。 当 $i \ge 10$ 时，$B(i)$ 含有因数 100，故 $B(i) % 100 = 0$ 恒成立。 只需找到 $A(i) % 100 = 0$ 的个数。$A(i)$ 为前缀和 $n(n+1)/2$。 $n(n+1)/2$ 是 100 的倍数等价于 $n(n+1)$ 是 200 的倍数。 根据周期规律，一个周期为 200，包含 4 个解（24, 175, 199, 200）。 遍历 0~9 找到符合条件的数，其余通过周期规律计算。 时间复杂度 $O(1)$。
