fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. ll const MX = (ll)1e5;
  5. long long const mod = (ll)1e9 + 7;
  6. bool num[MX];
  7. ll prime[MX];
  8.  
  9. void sieve() {
  10. 	num[0] = num[1] = 1;
  11.  
  12. 	for(int i = 4; i < MX; i += 2) {
  13. 		num[i] = 1;
  14. 	}
  15.  
  16. 	for(int i = 3; i < sqrt(MX); i += 2) {
  17. 		if(num[i] == 0) {
  18. 			for(int j = i * i; j < MX; j += i) {
  19. 				num[j] = 1;
  20. 			}
  21. 		}
  22. 	}
  23.  
  24. 	int k = 1;
  25. 	prime[0] = 2;
  26.  
  27. 	for(int i = 3; i < MX; i += 2) {
  28. 		if(num[i] == 0) {
  29. 			prime[k++] = i;
  30. 		}
  31. 	}
  32. }
  33.  
  34. ll BigMod(ll a, ll e) {
  35. 	if(e == -1) {
  36. 		e = mod - 2;
  37. 	}
  38.  
  39. 	ll r = 1;
  40.  
  41. 	while(e) {
  42. 		if(e & 1) {
  43. 			r *= a, r %= mod;
  44. 		}
  45.  
  46. 		a *= a, a %= mod, e >>= 1;
  47. 	}
  48.  
  49. 	return r % mod;
  50. }
  51.  
  52. int main() {
  53. 	//freopen("output.txt","w",stdout);
  54. 	sieve();
  55. 	ll n, a, m;
  56. 	int t;
  57. 	scanf("%d", &t);
  58.  
  59. 	for(int cs = 1; cs <= t; cs++) {
  60.  
  61. 		scanf("%lld%lld", &n, &m);
  62. 		ll sq = sqrt(n);
  63. 		ll cnt = 0;
  64. 		ll sum = 1;
  65.  
  66. 		for(ll i = 0; i <= n; i++) {
  67. 			cnt = 0;
  68.  
  69. 			if(prime[i] * prime[i] > n) {
  70. 				break;
  71. 			}
  72.  
  73. 			while(n % prime[i] == 0) {
  74. 				n /= prime[i];
  75. 				cnt++;
  76. 			}
  77.  
  78. 			cnt = (cnt * m);
  79. 			ll x = BigMod(prime[i], cnt + 1) - 1;
  80. 			ll y = (BigMod(prime[i] - 1, -1) * x) % mod;
  81. 			sum = (sum * y) % mod;
  82. 		}
  83.  
  84. 		if(n != 1) {
  85. 			if(n % mod != 0) {
  86. 				ll x = BigMod(n, m + 1) - 1;
  87. 				ll y = (BigMod(n - 1, -1) * x) % mod;
  88. 				sum = (sum * y) % mod;
  89. 			}
  90. 		}
  91.  
  92. 		printf("Case %d: %lld\n", cs, sum % mod);
  93. 	}
  94. }
Success #stdin #stdout 0s 16112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6JrShM
language:
C++14 (gcc 8.3)
created:
5 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!