fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int g[1000005];
  4. int mod = 1e9 + 7;
  5. long long ltn(int a, int n, int m){
  6.     long long r=0;
  7.     for(;n>0;n>>=1,a=(a+a)%m)if(n&1)r=(r+a)%m; return r;
  8. }
  9. long long lltn(int a, int n, int m){
  10.     long long r=1;
  11.     a%=m;
  12.     for(;n>0;n>>=1,a=ltn(a,a,m))if(n&1)r=ltn(r,a,m);return r;
  13. }
  14.  
  15. long long c(int n, int k){
  16. 	return (ltn(g[n] , lltn(g[k], mod - 2, mod) ,mod) * lltn(g[n - k], mod - 2, mod) ) % mod;
  17. }
  18.  
  19. int main() {
  20. 	int x, y;
  21. 	cin >> x >> y;
  22. 	g[0] = 1;
  23.  
  24. 	for(int i = 1; i <= 1000000; i++){
  25. 		g[i] = (g[i - 1] * i) % mod;
  26. 	}
  27. 	if(y % x != 0) cout << 0;
  28. 	else{
  29. 		int k = y / x;
  30. 		vector<int> a;
  31. 		int i = 2;
  32. 		while(i * i <= k){
  33. 			if(k % i == 0){
  34. 				a.push_back(i);
  35. 				while(k % i == 0) k /= i;
  36. 			}
  37. 			i++;
  38. 		}
  39. 		if(k > 1) a.push_back(k);
  40.  
  41. 		k = y/x;
  42. 		long long res = 0;
  43. 		res = lltn(2, k - 1, mod);
  44.  
  45. 		int n = a.size();
  46. 		for (int i = 1; i < (1 << n); i++) {
  47. 			long long p = 1, cnt = 0;
  48. 			for (int j = 0; j < n; j++) {
  49. 				if (i & (1 << j)) { 
  50. 					cnt++;
  51. 					if(k / a[j] >= p){
  52. 						p *= a[j];
  53. 					}else{
  54. 						p = 0;
  55. 						break;
  56. 					}
  57. 				}
  58. 			}
  59. 			if(!p) continue;
  60. 			if(cnt % 2 == 0) res = (res + lltn(2, k/p - 1, mod)) % mod;
  61. 			else res = (res + mod - lltn(2, k/p - 1, mod)) % mod;
  62. 		}
  63. 		cout << lltn(2, k - 1, mod) << endl;
  64. 	}
  65. 	return 0;
  66. }
Success #stdin #stdout 0.02s 7492KB
comments (?)
stdin 
3 12
stdout 
8
https://ideone.com/u5jqFq
language:
C++14 (gcc 8.3)
created:
11 days 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!