int t, a, b, c, d, k; int pr[50005], mb[50005], sum[50005], tot; bool np[50005];
voidinit(){ mb[1] = 1; for (int i = 2; i <= 50000; i++) { if (!np[i]) pr[++tot] = i, mb[i] = -1; for (int j = 1; j <= tot && i * pr[j] <= 50000; j++) { np[i*pr[j]] = 1; if (i % pr[j] == 0) { mb[i*pr[j]] = 0; break; } else mb[i*pr[j]] = -mb[i]; } } for (int i = 1; i <= 50000; i++) sum[i] = sum[i-1] + mb[i]; }
intsolve(int nn, int mm){ int ret = 0, n = nn / k, m = mm / k; for (int l = 1, r = 0; l <= min(n, m); l = r + 1) { r = min(n / (n / l), m / (m / l)); ret += (sum[r] - sum[l-1]) * (n / l) * (m / l); } return ret; }