首页 > 代码库 > hud 4746 莫比乌斯反演

hud 4746 莫比乌斯反演

2024-07-12 09:32:52   221人阅读

Mophues

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 327670/327670 K (Java/Others)
Total Submission(s): 579    Accepted Submission(s): 235


Problem Description
As we know, any positive integer C ( C >= 2 ) can be written as the multiply of some prime numbers:
    C = p1×p2× p3× ... × pk
which p1, p2 ... pk are all prime numbers.For example, if C = 24, then:
    24 = 2 × 2 × 2 × 3
    here, p1 = p2 = p3 = 2, p4 = 3, k = 4

Given two integers P and C. if k<=P( k is the number of C‘s prime factors), we call C a lucky number of P.

Now, XXX needs to count the number of pairs (a, b), which 1<=a<=n , 1<=b<=m, and gcd(a,b) is a lucky number of a given P ( "gcd" means "greatest common divisor").

Please note that we define 1 as lucky number of any non-negative integers because 1 has no prime factor.
 

 

Input
The first line of input is an integer Q meaning that there are Q test cases.
Then Q lines follow, each line is a test case and each test case contains three non-negative numbers: n, m and P (n, m, P <= 5×105. Q <=5000).
 

 

Output
For each test case, print the number of pairs (a, b), which 1<=a<=n , 1<=b<=m, and gcd(a,b) is a lucky number of P.
 

 

Sample Input
210 10 010 10 1
 

 

Sample Output
6393
 

 

Source
2013 ACM/ICPC Asia Regional Hangzhou Online
 

 

#include <iostream>#include <cstring>#include <cstdio>using namespace std;typedef __int64 LL;const int maxn=5*1e5+5;int prime[maxn],mu[maxn],num,cnt[maxn],mbs[maxn][20];bool flag[maxn];void swap(int &a,int &b){ int t=a;a=b;b=t;}int min(int a,int b){return a<b?a:b;}void init(){    int i,j;    mu[1]=1;cnt[1]=0;    memset(flag,true,sizeof(flag));    for(i=2;i<maxn;i++)    {        if(flag[i])        {            prime[num++]=i;mu[i]=-1;cnt[i]=1;        }        for(j=0;j<num&&i*prime[j]<maxn;j++)        {            flag[i*prime[j]]=false;            cnt[i*prime[j]]=cnt[i]+1;            if(i%prime[j]==0)            {                mu[i*prime[j]]=0;break;            }            else mu[i*prime[j]]=-mu[i];        }    }    memset(mbs,0,sizeof(mbs));    for(i=1;i<maxn;i++)//求出单项的mbs[i][j]，表示的是i为公因子时的情况。    for(j=i;j<maxn;j+=i)        mbs[j][cnt[i]]+=mu[j/i];    for(i=1;i<maxn;i++)  //以下是求前缀和    for(j=0;j<19;j++)        mbs[i][j]+=mbs[i-1][j];    for(i=0;i<maxn;i++)    for(j=1;j<19;j ++)        mbs[i][j]+=mbs[i][j-1];}int main(){    num=0;    init();    int i,j,t,n,m,p;    scanf("%d",&t);    while(t--)    {        scanf("%d %d %d",&n,&m,&p);        if(p>=19){ printf("%I64d\n",(LL)n*m);continue;}        if(n>m) swap(n,m);        LL ans=0;        for(i=1,j=1;i<n;i=j+1)        {            j=min(n/(n/i),m/(m/i));            ans+=(LL)(mbs[j][p]-mbs[i-1][p])*(n/i)*(m/i);        }        printf("%I64d\n",ans);    }    return 0;}


联系
我们