输入a b c d k求有多少对x y 使得x在a-b区间 y在c-d区间 gcd(x, y) = k 此外a和c一定是1
由于gcd(x, y) == k 将b和d都除以k 题目转化为1到b/k 和1到d/k 2个区间 如果第一个区间小于第二个区间 讲第二个区间分成2部分来做1-b/k 和 b/k+1-d/k
第一部分对于每一个数i 和他互质的数就是这个数的欧拉函数值 全部数的欧拉函数的和就是答案
第二部分能够用全部数减去不互质的数 对于一个数i 分解因子和他不互质的数包括他的若干个因子 这个用容斥原理 奇加偶减
#include#include #include using namespace std;typedef __int64 LL;const int maxn = 100010;LL phi[maxn];LL sum[maxn], p[maxn][33];void phi_table(int n){ memset(sum, 0, sizeof(sum)); memset(phi, 0, sizeof(phi)); phi[1] = 1; for(int i = 2; i <= n; i++) { if(!phi[i]) for(int j = i; j <= n; j += i) { if(!phi[j]) phi[j] = j; phi[j] = phi[j] / i * (i-1); p[j][sum[j]++] = i; } phi[i] += phi[i-1]; }}void dfs(int id, LL num, LL cnt, int a, LL& ans, int x){ if(id == sum[x]) { if(cnt == 0) return; if(cnt&1) ans += a/num; else ans -= a/num; return; } dfs(id+1, num*p[x][id], cnt+1, a, ans, x); dfs(id+1, num, cnt, a, ans, x);}LL cal(int x, int a){ LL ans = 0; dfs(0, 1, 0, a, ans, x); return ans;}int main(){ phi_table(100000); int cas = 1; int T; scanf("%d", &T); while(T--) { int a, b, k; scanf("%d %d %d %d %d", &a, &a, &b, &b, &k); if(!k) { printf("Case %d: %d\n", cas++, 0); continue; } if(a > b) swap(a, b); a /= k; b /= k; LL ans = phi[a]; for(int i = a+1; i <= b; i++) ans += a-cal(i, a); printf("Case %d: %I64d\n", cas++, ans); } return 0;}