fork(2) download
copy 
  1. #include<stdio.h>
  2. #include<math.h>
  3. typedef long long int ll;
  4. ll gcd(ll a,ll b){
  5.     if(a%b==0)
  6.         return b;
  7.     else
  8.        return gcd(b,a%b);
  9.     }
  10. ll power(ll a,ll m){
  11.     a=(a*a)%m;
  12.     return (a*a)%m;
  13. }
  14. ll power_q(ll n, ll m){
  15.     ll ans,x,k,denom =30;
  16.     ans=(n/gcd(n,denom));
  17.     denom/=gcd(n,denom);
  18.     k=((n+1)/gcd(n+1,denom));
  19.     ans=ans*k;
  20. if(ans>m)
  21.     ans%=m;
  22.     denom/=gcd(n+1,denom);
  23.     k =((2*n+1)/gcd(2*n+1,denom));
  24.     ans=ans*k;
  25. if(ans>m)
  26.     ans%=m;
  27.  
  28.     denom/=gcd(2*n+1,denom);
  29. if(denom==1){
  30.     k=(3*(n%m)*((n+1)%m )-1);
  31. if(k<0)
  32.     k+=m;
  33.     ans=ans*k;
  34.     if(ans>m)
  35.     ans%=m;
  36. }
  37. else{
  38.     if(n%5==1)
  39.     {
  40.     x=n/5;
  41.     k=(3 *(5*(x*x)%m+ 3*x) + 1);
  42.     ans=ans*k;
  43.     //cout<<"k1 "<<k<<"ans= "<<ans<<endl;
  44.     if(ans>m)
  45.         ans%=m;
  46.     }
  47.     else
  48.     {
  49.     x=n/5;
  50.     k=(3*(5*(x*x)%m+7*x)+7);
  51.     ans=ans*k;
  52.   //  cout<<"k2= "<<k<<"ans= "<<ans<<endl;
  53.     if(ans>m)
  54.         ans%=m;
  55.         }
  56. }
  57.     return ans;
  58. }
  59. int main(){
  60.     int t;
  61.      ll ans,i,n,m,root,p,q,r,z;
  62.     scanf("%d",&t);
  63. while(t--){
  64.     ans=0;
  65.     scanf("%lld%lld",&n,&m);
  66. if(n<2){
  67. printf("%lld\n",n);
  68.     continue;
  69.     }
  70.  root = sqrt(n*1.0D);
  71. for(i=1;i<=n/(root+1);i++ ){
  72.     ans+=((n/i-root)*power(i,m));
  73.     if(ans>m)
  74.     ans%=m;
  75.     if(n/i==10000000000){
  76.         p=(1000000000)%m;
  77.         q=(10000000001)%m;
  78.         r=((2*n+1)/3)%m;
  79.     z=(((((3*n)%m)*((n+1)%m))%m)-1+m)%m;
  80.     ans+=(((p*q)%m)*((r*z)%m))%m;
  81.      // printf("%lld %lld %lld\n",p,q,r);
  82.      // printf("%lld %lld\n",z,xi);
  83.     }
  84.     else
  85.     ans+=power_q(n/i,m);
  86.     if(ans>m)
  87.     ans%=m;
  88.     }
  89. if(root==i){
  90. ans=ans+power_q(n/i,m);
  91.     if(ans>m)
  92.     ans%=m;
  93. }
  94. printf("%lld\n",(ans)%m);
  95. }
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0.4s 3348KB
comments (?)
stdin
copy 
15
10000000000 100000
10000000000 35452
10000000000 92324
10000000000 6
1000000000 2434
100000000 100000
10000000 100000
1000000 100000
1000 100000
2000000 100000
10000 100000
100000 100000
4 12314
999999999 100000
11111111 1111
stdout
copy 
Standard output is empty
https://ideone.com/RDyRao
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!