fork(2) download
copy 
  1. //2500186
  2. //Sreejata Kishor Bhattacharya
  3. #include <iostream>
  4. #include <vector>
  5. #include <math.h>
  6. #include <set>
  7. #include <algorithm>
  8. #include <map>
  9. using namespace std;
  10. long long int modul(long long int n, long long int m){
  11.     long long int t=1;
  12.     for (int i=0; i<n; i++){
  13.         t= t*2;
  14.         t=t%m;
  15.     }
  16.     return t;
  17. }
  18.  
  19. long long int f[150000], g[150000];
  20.  
  21. int main() {
  22.     long long int n, m, j;
  23.     cin>>n;
  24.     cin>>m;
  25.     float t= sqrt(n);
  26.     t= floor(t);
  27.     j= (long long int) t;
  28.  
  29.     long long int ir= 0;
  30.  
  31.     for (int i=1; i<=j; i++){
  32.         if (n%i==0){
  33.             if (i!=n/i){
  34.             f[ir]= i;
  35.             f[ir+1]= n/i;
  36.                ir+=2;
  37.             }
  38.             else {
  39.                 f[ir]= i;
  40.                 ir+=1;
  41.             }
  42.  
  43.         }
  44.     }
  45.     sort(f, f+ir);
  46.  
  47. /*
  48.     map <int, int> t;
  49.     t[1]= 2%m;
  50.     for (int i=0; i<150001; i++){
  51.         t[i+1]= 2*t[i];
  52.         t[i+1]= t[i+1]%m;
  53.     }
  54. */
  55.     map <int, int> tu;
  56.     tu[1]= 2%m;
  57.     for (int i=1; i<150001; i++){
  58.         tu[i+1]= 2*tu[i];
  59.         tu[i+1]= tu[i+1]%m;
  60.     }
  61.     g[0]= modul(1, m);
  62.     for (int i=1; i<ir; i++){
  63. /*
  64.         int sum= 0, t= t[f[i]];
  65. */
  66.         int sum= 0, t= tu[f[i]];
  67.         for (int t=0; t<i; t++){
  68.             if (f[i]%f[t]==0){
  69.                 sum+=g[t]%m;
  70.             }
  71.             sum= sum%m;
  72.  
  73.         }
  74.         g[i]= t-sum;
  75.      // g[i]= g[i]%m;
  76.        g[i]= g[i]%m;  
  77.         if (g[i]<0){
  78.         	g[i]= m+g[i];
  79.         	g[i]= g[i]%m;
  80.         }
  81.        // (didn't include the if(g[i]<0) part in my original submission 
  82.  
  83.     }
  84.  
  85.     cout<<g[ir-1]<<endl;
  86.  
  87.  
  88.     return 0;
  89. }
  90.  
Success #stdin #stdout 0.13s 10248KB
comments (?)
stdin
copy 
146160 99999989
stdout
copy 
73149428
https://ideone.com/MaHnLi
language:
C++ (gcc 8.3)
created:
9 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!