洛谷P2257 YY的GCD

今日份是数论

大概是。。从小学奥数到渐渐毒瘤

那就简单列一下目录【大雾

同余质数密度唯一分解定理互质

完全剩余系简化剩余系欧拉函数逆元斐蜀定理

阶（及其性质）欧拉定理费马小定理原根调和级数

欧拉函数推广到积性函数完全积性函数

莫比乌斯函数莫比乌斯反演

狄利克雷卷积杜教筛 Lucas定理

回到这道题

题意：

给出n, m ∈ [1, 1e7] ，求有多少对(x, y)

满足x ∈ [1, n]， y ∈ [1, m] 且 gcd(x, y) 为质数

字丑【痛心

洛谷P2257 YY的GCD

附上代码

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int N = 1e7 + ;

 int prm[N], mu[N], ps;

 bool ism[N];

 long long res[N], g[N];

 inline void calc(int n){

     mu[] = ;

     for(int i = ; i <= n; i++){

         if(!ism[i]) {prm[++ps] = i; mu[i] = -;}

         for(int j = ; j <= ps && prm[j] * i <= n; j++){

             ism[prm[j] * i] = ;

             if(!(i % prm[j])) break;

             mu[prm[j] * i] = -mu[i];

         }

     }

     for(int i = ; i <= ps; i++)

         for(int j = ; j * prm[i] <= n; j++)

             g[j * prm[i]] += mu[j];

     for(int i = ; i <= n; i++)

         res[i] = res[i - ] + (long long) g[i];

 }

 int main(){

     int T; scanf("%d", &T);

     long long ans;

     int n, m;

     calc(1e7);

     while(T--){

         scanf("%d%d", &n, &m);

         if(n > m) swap(n, m);

         ans = ;

         int i = , j;

         while(i <= n){

             j = min(n / (n / i), m / (m / i));

             ans += (long long)(n / i) * (m / i) * (res[j] - res[i - ]);

             i = j + ;

         }

         printf("%lld\n", ans);

     }

     return ;

 }

秒客网

洛谷P2257 YY的GCD

相关文章