fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef unsigned long long ll;
  4. #define MAX 99999999
  5. //const ll mod = 1000000007;
  6. bool primes[MAX+5];
  7. ll prime[5761500];
  8. ll counter = 0;
  9.  
  10. void sieve()
  11. {
  12. 	memset(primes, false, sizeof(primes));
  13. 	for(ll i = 2; i * i < MAX; i++)
  14. 		if(!primes[i])
  15. 		{
  16. 			prime[counter++] = i;
  17. 			for(ll j = i*2; j < MAX; j += i)
  18. 			primes[j] = true;
  19. 		}
  20. }
  21.  
  22. ll power(ll x, ll y)
  23. {
  24. 	ll count = 0;
  25. 	ll z = y;
  26. 	while(x >= z)
  27. 	{
  28. 		count += (x/z);
  29. 		z *= y;
  30. 	}
  31. 	return count;
  32. }
  33. ll mulmod(ll a, ll b, ll mod)
  34. {
  35.     ll res = 0; 
  36.     a = a % mod;
  37.     while (b > 0)
  38.     {
  39.         if (b % 2 == 1)
  40.             res = (res + a) % mod;
  41.         a = (a * 2) % mod;
  42.         b /= 2;
  43.     }
  44.     return res % mod;
  45. }
  46.  
  47.  
  48. int main() 
  49. {
  50. 	//your code goes here
  51. 	ios_base::sync_with_stdio(false);	cin.tie(0);	cout.tie(0);
  52. 	ll t, n;
  53. 	sieve();
  54. 	cin>>t;
  55. 	while(t--)
  56. 	{
  57. 		ll m;    cin>>n>>m;
  58. 		ll ans=1;
  59. 		for(ll i = 0; i < counter; i++)
  60. 		{
  61. 			if(prime[i]%2 == 0) continue;
  62. 			ll powers = power(n, prime[i]);
  63. 			if(powers == 0) 	break;
  64. 			ans = mulmod(ans, powers+1, m)%m;
  65. 		}
  66. 		if(((ans - 1) % m) < 0)
  67. 			printf("%lld\n", ((ans - 1 + m) % m));
  68. 		else
  69. 			printf("%lld\n", (ans - 1) % m);
  70. 	}
  71. 	return 0;
  72. }
Success #stdin #stdout 1.28s 157888KB
comments (?)
stdin
copy 
1
3 7
stdout
copy 
1
https://ideone.com/XHpeaq
language:
C++14 (gcc 8.3)
created:
6 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!