南京理工大学第8回プログラム設計大会C Count_Prime Solution

Descriptionはあなたに1つの数nを与えて、あなたは[a,b]のこの区間の中でnの互質の数の個数を統計してください.2つの数は互いに質的であり、彼らが1を除いて他の共通因子がない場合、または彼らの最大の共通因子が1である場合のみである.1と任意の数は互いに素である.Inputの最初の行には、T組のテストデータを表す整数T(1<=T<=100)が入力される.次に、T行には、1行あたり3個の整数a,b,n(1<=a<=b<=10^15,1<=n<=10^9)がスペースで区切られている.Outputは、nとの互質を表す整数の数を出力する.Sample Input
2 1 10 2 3 10 5
Sample Output
5 6
はっきり言えない気がするので、NJUST comzyhの問題解を引用してみましょう.要するに分解+反発の原理です
反発原理、まずnに対して質量因数を分解し、それぞれ各質量因数を記録すると、求めた区間内である質量因数と相容れない個数がn/r(i)であり、r(i)がrのある質量因数であると仮定すると3つの質量因数しかないと仮定し、総相容れない個数はp 1+p 2+p 3-p 2-p 3-p 2 p 3+p 1 p 2*p 3であるべきであり、piはn/r(i)、すなわちある質量因数と相容れない数の個数を表す.より多くの質量因子がある場合,状態圧縮で解決でき,この質量因子が取り込まれたことをバイナリビットで1で示す.奇数個の1があれば加算され、逆に減算されます.

C++ Code
#include 
#include 
#include 
#include 
using namespace std;
const int inf=0x3f3f3f3f;
const double pi= acos(-1.0);
const double esp=1e-6;
const int MAX=2*1e5+10;
long long prime[MAX];
long long sprime[MAX];
bitset pri;
long long k,cnt;
void is_prime() {
    pri.set();
    for(long long i=2; iif(pri[i]) {
            prime[k++]=i;
            for(long long j=i+i; j0;
        }
    }
}
void Divide(long long n) {
    cnt=0;
    long long t=(long long)sqrt(1.0*n);
    for(long long i=0; prime[i]<=t; i++) {
        if(n%prime[i]==0) {
            sprime[cnt++]=prime[i];
            while(n%prime[i]==0)
                n/=prime[i];
        }
    }
    if(n>1)
        sprime[cnt++]=n;
}
long long Ex(long long n) {
    long long q[MAX];
    long long sum=0;
    long long t=1;
    q[0]=-1;
    for(long long i=0; ilong long x=t;
        for(long long j=0; j1);
            t++;
        }
    }
    for(long long i=1; ireturn sum;
}
int main() {
    int T;
    int icase=1;
    long long A,B,N;
    long long res;
    is_prime();
    cin>>T;
    while(T--) {
        cin>>A>>B>>N;
        Divide(N);
        res=(B-Ex(B))-(A-1-Ex(A-1));
        cout<return 0;
}