hdu4135(容斥原理)Co-prime

2017年07月23日 10点热度 0人点赞 0条评论

题目大意是:输入A,B,N,求[A,B]区间内与N互质的数的个数 

#include
#include
#include
using namespace std;
long long a,b;
int k;
vector x;
void getprime(int n)
{
    x.clear();
    for(int i=2; i*i<=n; ++i)
        if(n%i==0)
        {
            x.push_back(i);
            n/=i;
            while(n%i==0) n/=i;
        }
    if(n!=1) x.push_back(n);//这个需要注意
}
long long solve(long long n,long long b)
{
    //求n和区间[1,b]
    long long ans=b;
    for(int i=1; i<(1<>a>>b>>k;
        if(!k)
        {
            printf("Case %d: 0n",kase);
            continue;
        }
        getprime(k);
        printf("Case #%d: %lldn",kase,solve(k,b)-solve(k,a-1));
    }
    return 0;
}
未经允许不得转载!hdu4135(容斥原理)Co-prime

update

纸上得来终觉浅, 绝知此事须躬行。