Coprime Conundrum 容斥原理-白红宇

Coprime Conundrum 容斥原理

阅读量：5275 次

发布时间：2019-06-14

本文共 2503 字，大约阅读时间需要 8 分钟。

我们可以枚举每一个p在[2, sqrt(n)]里，然后就是在[p + 1, n / p]中找有多少个数和p互质了。

标准容斥，先算出[1, n / p]中有多少个和p互质，这个是不能用欧拉定理做的，需要把p质因数分解，然后dfs

求解元素X在区间[1, up]中，有多少个数和X互质。（容斥）

思路：把X质因数分解，多了的不要。12 = 2 * 3。然后有个明显的道理就是如果是2的倍数的话，那么就一定不会与12互质，所以需要减去2的倍数，减去3的倍数，再加上6的倍数。容斥的思路好想，但是不怎么好写。所以结果是总数量up – 不互质的个数。

预处理；his[val][]表示元素val拥有的质因子，Size[val]表示有多少个。记得1是不做任何处理的。就是Size[1] = 0。Dfs的cur表示下一次从哪里开始，不往回枚举，就是任意k个值。

int calc(int up, int cur, int number, int tobuild, int flag) { //一开始flag是0。0表示加，1减

int ans = 0;

for (int i = cur; i <= Size[number]; ++i) {

if (flag == 0) {

ans += up / (his[number][i] * tobuild);

} else ans -= up / (his[number][i] * tobuild);

ans += calc(up, i + 1, number, his[number][i] * tobuild, !flag);

}

return ans;

}

计算12在[1, 24]就是24 - calc(24, 1, 12, 1, 0)。tobuild是选择k个质因数后生成的数字。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   const int maxn = 50000 + 20;int prime[maxn];bool check[maxn];int total;int Size[maxn];int his[maxn][50 + 20];void initprime() { for (int i = 2; i <= maxn - 20; i++) { if (!check[i]) { prime[++total] = i; } for (int j = 1; j <= total; j++) { if (i * prime[j] > maxn - 20) break; check[i * prime[j]] = 1; if (i % prime[j] == 0) break; } } for (int i = 1; i <= maxn - 20; ++i) { int t = i; for (int j = 1; j <= total; ++j) { if (prime[j] > t) break; if (t % prime[j] == 0) { his[i][++Size[i]] = prime[j]; while (t % prime[j]) { t /= prime[j]; } } } } return ;}LL calc(int up, int cur, int number, int tobuild, int flag) { LL ans = 0; for (int i = cur; i <= Size[number]; ++i) { if (flag == 0) { ans += up / (his[number][i] * tobuild); } else ans -= up / (his[number][i] * tobuild); ans += calc(up, i + 1, number, his[number][i] * tobuild, !flag); } return ans;}void work() { int n; cin >> n; int en = (int)sqrt(n + 0.5);// cout << en << endl; LL ans = 0; for (int i = 2; i <= en; ++i) { ans += n / i - calc(n / i, 1, i, 1, 0); ans -= i - calc(i, 1, i, 1, 0);// cout << calc(n / i, 1, i, 1, 0) << " " << calc(i, 1, i, 1, 0) << endl;// cout << ans << endl; } cout << ans << endl;}int main() {#ifdef local freopen("data.txt", "r", stdin);// freopen("data.txt", "w", stdout);#endif initprime(); work(); return 0;}

View Code

转载于:https://www.cnblogs.com/liuweimingcprogram/p/6159195.html

你可能感兴趣的文章