Saleh127

Light oj(LO) 1054

Apr 13th, 2021
206
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.67 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5. #define maX 100000
  6. vector<ll>p;
  7. ll mod=1e9+7;
  8. bool marked[maX+2];
  9. void sieve()
  10. {
  11. marked[0]=1;
  12. marked[1]=1;
  13. for(ll i=4; i<=maX; i+=2)
  14. {
  15. marked[i]=1;
  16. }
  17. p.push_back(2);
  18. for(ll i=3; i<=maX; i+=2)
  19. {
  20. if(marked[i]==0)
  21. {
  22. p.push_back(i);
  23. for(ll j=i*i; j<=maX; j+=i+i)
  24. {
  25. marked[j]=1;
  26. }
  27. }
  28. }
  29. }
  30.  
  31. ll bigmod(ll a,ll c,ll d)
  32. {
  33. if(c==0) return 1LL;
  34. ll x=bigmod(a,c/2,d);
  35. x=x*x%d;
  36. if(c%2==1)
  37. {
  38. x=(x*a)%d;
  39. }
  40. return x;
  41. }
  42.  
  43. int main()
  44. {
  45. ios_base::sync_with_stdio(0);
  46. cin.tie(0);
  47. cout.tie(0);
  48.  
  49. sieve();
  50.  
  51. test
  52. {
  53.  
  54. ll n,m,i,j,k,l,ans=1,c,a,b;
  55.  
  56. cin>>n>>m;
  57.  
  58. for(i=0; i<p.size() && p[i]*p[i]<=n; i++)
  59. {
  60. if(n%p[i]==0)
  61. {
  62. c=0;
  63. while(n%p[i]==0)
  64. {
  65. c++;
  66. n/=p[i];
  67. }
  68.  
  69. a=((bigmod(p[i],c*m + 1LL ,mod)-1LL)+mod)%mod;
  70.  
  71. b=bigmod(p[i]-1LL,mod-2LL,mod)%mod;
  72.  
  73. ans=(ans%mod * a%mod * b%mod)%mod;
  74. }
  75. }
  76.  
  77. if(n>1)
  78. {
  79. a=((bigmod(n,m+1,mod)-1LL)+mod)%mod;
  80.  
  81. b=bigmod(n-1LL,mod-2,mod)%mod;
  82.  
  83. ans=(ans%mod * a%mod * b%mod)%mod;
  84. }
  85.  
  86. cout<<"Case "<<cs<<": "<<ans<<endl;
  87. }
  88.  
  89. return 0;
  90. }
  91. /// sum of div -- (n^(r+1)-1)/(n-1) for every prime n with r frequency
Advertisement
Add Comment
Please, Sign In to add comment