已知x是1到n之间的数字,y是1到m之间的数字,两者都是闭区间,问有多少对(x,y)满足x和y之积为平方数。
3和12、48是等价的,因为12=3乘以2的平方,48=3乘以4的平方。
只需要找到每个等价类包含多少个数字,那么相同等价类之积必然是平方数。
那么又有问题了:如果是立方数呢?那就需要改成二维数组,3的等价类有两种:一种是2次幂等价类,一种是一次幂等价类。
import java.util.Scanner;
public class Main {
int[] get(int n) {
int[] a = new int[n + 1];
for (int i = 1; i <= n; i++) {
if (a[i] == -1) continue;
int s = 0;
for (int j = 1; j * j * i <= n; j++) {
if (a[j * j * i] != -1) {
s++;
a[j * j * i] = -1;
}
}
a[i] = s;
}
return a;
}
int solve(int n, int m) {
if (n < m) {
int temp = m;
m = n;
n = temp;
}
int[] a = get(n);
int[] b = get(m);
int s = 0;
for (int i = 0; i <= m; i++) {
if (a[i] != -1) {
s += a[i] * b[i];
}
}
return s;
}
Main() {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt(), m = cin.nextInt();
int s = solve(n, m);
System.out.println(s);
}
public static void main(String[] args) {
new Main();
}
}