牛客寒假算法训练1 D 欧拉（容斥）


 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1000000;
 4 typedef long long ll;
 5 int p[maxn],a[maxn];
 6     ll n,k,A,B;
 7 const int mod=1e9+7;
 8 
 9 ll Pow(ll x,ll n)
10 {
11     ll res=1;
12     while(n>0)
13     {
14        if(n%2==1)  
15        {
16          res=res*x;
17          res=res%mod;
18        }
19        x=x*x;
20        x=x%mod;
21        n>>=1;
22     }
23     return res;
24 }
25     long long z,sum=0;
26     ll flag=0;
27 ll cal(ll n=600){    
28     ll res=0;
29     for(ll i=1;i<(1<<flag);i++){
30         ll t=i,tmp=1,k=0;
31         ll len=0;
32         while(t){
33             if(t&1){
34                 tmp*=a[k];
35                 len++;
36             }
37             t>>=1;
38             k++;
39         }
40         //cout<<tmp<<"fuck"<<endl;
41         if(len&1) res+=(tmp+n/tmp*tmp)*n/tmp/2;//等差数列和
42         else res-=(tmp+n/tmp*tmp)*n/tmp/2;
43         res%=mod-1;
44     }
45     return res;
46 }
47 
48 int main(){
49 
50 cin>>n>>k>>A>>B;
51 sum=0;
52  z=n;
53  flag=0;
54     for(ll i=2;i<=n;){
55         if(n%i==0){
56             while(n%i==0){
57                 p[i]++;
58                 n/=i;
59             }
60             a[flag++]=i;
61         }
62         if(i==2)i++;
63         else i+=2;
64     }
65    sum=cal(z);
66   // cout<<sum<<endl;
67     long long x=(z)*(z+1)/2;
68     x-=sum;
69     x%=mod-1;
70     long long ans=(A+B)%mod*Pow(k,x%(mod-1)+mod-1)%mod;
71     cout<<ans<<endl;
72     return 0;
73 }