fork download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<algorithm>
  4. #include<math.h>
  5. #include<bits/stdc++.h>
  6. #include<stack>
  7. #include<queue>
  8. #include<list>
  9. #include<vector>
  10. #include<bitset>
  11. // #include<unordered_map> 
  12. #include <ext/pb_ds/assoc_container.hpp>
  13. #include <ext/pb_ds/tree_policy.hpp>
  14. // #include "boost/algorithm/string.hpp"
  15. #define fio ios_base::sync_with_stdio(false)
  16. #define mod 1000000007
  17. #define mod1 mod
  18. #define mod2 100000009
  19. #define li long long int
  20. #define ll li
  21. #define readi(x) scanf("%d",&x)
  22. #define  reads(x)  scanf("%s", x)
  23. #define readl(x) scanf("%I64d",&x)
  24. #define rep(i,n) for(i=0;i<n;i++)
  25. #define revp(i,n) for(i=(n-1);i>=0;i--)
  26. #define myrep1(i,a,b) for(i=a;i<=b;i++)
  27. #define myrep2(i,a,b) for(i=b;i>=a;i--)
  28. #define pb push_back
  29. #define mp make_pair
  30. #define fi first
  31. #define sec second
  32. #define MAXN 1000000000000000000
  33. #define MINN -1000000000000000000
  34. #define pii pair<ll,ll> 
  35. #define pdd pair<double,double>
  36. #define pic pair<int,char>
  37. #define N 200010
  38. #define lgn 20
  39. #define ddouble long double
  40. #define minus minu
  41. #define PI 3.1415926535
  42. #define lgn 20
  43.  
  44.  
  45. // #define INTMAX 200000000
  46.  
  47. // using namespace boost;
  48. // #define si short int
  49.  
  50. using namespace std;
  51. using namespace __gnu_pbds;             
  52. // typedef priority_queue<ll, vector<ll> > max_pq;
  53. // typedef priority_queue<pii, vector<pii> , greater<pii >  > min_pq;
  54. ll toint(const string &s) {stringstream ss; ss << s; ll x; ss >> x; return x;}
  55. string tostring ( ll number ){stringstream ss; ss<< number; return ss.str();}
  56.  
  57. // typedef priority_queue<pair < ll , pair < pii , ll > >  , vector<pair < ll , pair < pii , ll > >  > ,greater<pair < ll , pair < pii , ll > >  > > min_pq;
  58. // #define TRACE
  59. // #ifdef TRACE
  60. // #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  61. //     template <typename Arg1>
  62. //     void __f(const char* name, Arg1&& arg1){
  63. //         cout << name << " : " << arg1 << std::endl;
  64. //         //use cerr if u want to display at the bottom
  65. //     }
  66. //     template <typename Arg1, typename... Args>
  67. //     void __f(const char* names, Arg1&& arg1, Args&&... args){
  68. //         const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  69. //     }
  70. // #else
  71. // #define trace(...)
  72. // #endif
  73.  
  74. typedef tree< ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > OST;
  75. typedef priority_queue< pii , vector<pii> > max_pq;
  76. typedef priority_queue<pii, vector<pii> , greater <pii>  > min_pq;
  77.  
  78.  
  79. ll x,y;
  80. map < ll, ll > dp;
  81.  
  82. ll modex ( ll a, ll b )
  83. {
  84.     ll res = 1;
  85.     while ( b )
  86.     {
  87.         if ( b%2 )
  88.         {
  89.             res = (res*a)%mod;
  90.         }
  91.         a = (a*a)%mod;
  92.         b/=2;
  93.     }
  94.     return res;
  95. }
  96.  
  97. ll solve(ll x )
  98. {
  99.     if ( x == 1 )
  100.         return 1;
  101.     else if ( dp[x] )
  102.         return dp[x];
  103.     else
  104.     {
  105.         ll ret = modex(2,x-1);
  106.         for ( ll i = 2; i <= sqrt(x); i ++)
  107.         {
  108.             if ( x%i == 0 )
  109.             {
  110.                 ret = (ret - (solve(i))+mod)%mod;
  111.                 if ( x/i != i )
  112.                     ret = (ret - (solve(x/i))+mod)%mod;       
  113.             }
  114.         }
  115.         return dp[x]= (ret-1+mod)%mod;
  116.     }
  117.  
  118. }
  119.  
  120. int main()
  121. {
  122.     ios::sync_with_stdio(false);
  123.     cin.tie(NULL);
  124.     #ifndef ONLINE_JUDGE
  125.     freopen("input.txt","r",stdin);
  126.     freopen("output.txt","w",stdout);
  127.     #endif
  128.     cin >> x >> y;
  129.     // return 0;
  130.     if ( y%x == 0 )
  131.     {
  132.         ll numb = (y/x);
  133.         if ( y == x )
  134.         {
  135.             cout <<"1";
  136.             return 0;
  137.         }
  138.         // ll ans = 0;
  139.         // ll temp = numb;
  140.         // ll tot = 1;
  141.         // for ( ll i = 2; i <= sqrt(numb); i ++)
  142.         // {
  143.         //     if ( temp%i == 0 )
  144.         //     {
  145.         //         tot = (tot*(i-1))/i;
  146.         //         while ( temp%i == 0 )
  147.         //         {
  148.         //             temp/=i;
  149.         //         }
  150.         //     }
  151.         // }
  152.         // if ( temp != 1)
  153.         //     tot = (tot*(temp-1))/temp;
  154.         // ans = tot%mod;
  155.         cout << (solve(y/x))%mod;
  156.  
  157.  
  158.  
  159.     }
  160.     else
  161.     {
  162.         cout <<"0";
  163.     }
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170. }
Runtime error #stdin #stdout 0s 4140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PvYJio
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!