莫比乌斯变换.ppt

LL Solve(int n){ LL ans = 0; for(int i=0; ikp[i]=n; i++) ans += 1 + f[n/p[i]]; return ans; } int main() { Init(); isprime(); int n; scanf(%d,n); printf(%I64d\n,Solve(n)); return 0; } * 例2、公因数为质数问题-进一步 /acdreamers/article/details/8542292#comments 问题描述：给定正整数m, n，其中n=107，求使得gcd(x,y)为质数的(x,y)的个数，1=x=m， 1=y=n 。 分析：用莫比乌斯反演来解决。 * 例 解：记A={gcd(x,y): 1?x ?n，1 ?y ?m}； f(d)=| {gcd(x,y): gcd(x,y)=d，1?x ?n，1 ?y ?m} |，即A中使得gcd(x,y)=d的数的个数。 再记 即 F(k)是满足 k | gcd(x,y)的数对(x, y)的个数。 那么，显然 根据反演公式 题目要求gcd(x,y)为质数，那么我们枚举每一个质数q，然后得到 本题需要优化 用Eratosthenes筛法的尝试 设A为a在[1, m]，b在[1, n]的所有自然数对(x, y)的gcd序列，即 A=gcd(x, y)：若1? x ? m, 1? y ? n ，A共有mn个元素， Ad= gcd(x,y)：若d | gcd(x,y) ,且x ? n, y ? n ，显然 |Ad|=[m/d]?[n/d] * 分析 对于正整数q， 序列A中与q互质的整数a的个数为 题目要求gcd(x, y)是质数，现枚举每一个质数q。 对于固定的质数q，序列A中使与q不互质的整数a就是使得gcd(x, y)=q的数，个数为mn-Sq。 因此，序列A中为质数的整数a个数为 * 例3、Mophues Source：/showproblem.php?pid=4746 Description: 任何整数C ( C = 2 )都可以写成素数之积C = p1×p2× p3× ... × pk其中， p1, p2 ... pk 是素数。如 C = 24, 则 24 = 2 × 2 × 2 × 3, 其中, p1 = p2 = p3 = 2, p4 = 3, k = 4.给定两整数 P和 C, 若 k=P ( k是 C的素因子个数),称 C是P的幸运数.现小X需计算的点对 (a, b)的个数,其中1=a=n , 1=b=m, gcd(a,b)是 P的幸运数 ( “gcd”是最大公因数).注意：因为1无素因子，定义1为任何非负数的幸运数. * Input 首行有一个整数 T，表示有 T 组测试数据.接下来有T行，每行是一种测试数据，含3个非负整数n, m 与P (n, m, P = 5×105. T =5000). Output 对每种测试数据，输出对 (a, b)的个数，其中 1=a=n , 1=b=m, 且 gcd(a,b) 是 P的幸运数. * Sample Input 2 10 10 0 10 10 1 Sample Output 63 93 Mophues分析 题意：给出n, m, p，求(a, b)的对数：满足 gcd(a, b)的素因子个数=p，(其中1=a=n, 1=b=m) 分析：设f(d)：gcd(a, b)=d的(a,b)的组数， F(k): k| gcd(a, b) 的(a,b)的组数， 易知F(k) = [n/k]*[m/k]； 对整数k，枚举k的素因子个数使得总数=p，这种k记作k(p) k(p)=k，当k的素因子个数不超过p k(p)=0，当k的素因子个数超过p。 程序实现：见下页 include cstdio #include cstdlib #include iostream using namespace std; const int M = 555555, int N = 19; int g[M][N], num[M]; int pri[M],pnum,mu[M],vis[M]; int calc(int y,int x){ //统计y中因子x出现的次数 int ret = 0; while(y%x==0){ ret++; y /= x; } return ret; } * int main(){ int T,n,m,P,