fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define f first
  4. #define s second
  5. #define pb push_back
  6. #define mp make_pair
  7. #define mod 1000000007LL
  8. #define ll long long
  9. #define pii pair<int,int>
  10. #define pil pair<int,ll>
  11. #define pll pair<ll,ll>
  12. #define pli pair<ll,int>
  13. #define beg begin()
  14. #define sz size()
  15. #define itr iterator
  16. #define piii pair<int, pii >
  17. ll md[100011];
  18. ll solve (ll a, ll b, ll m)
  19.  {
  20.     ll ans1 = 100*m;
  21.     ll n = (ll) sqrt (m + .0) + 1;
  22.  
  23.     ll an = 1;
  24.     for (ll i=0; i<n; ++i)
  25.         an = (an * a) % m;
  26.  
  27.     map<ll,ll> vals;
  28.     for (ll i=1, cur=an; i<=n; ++i) {
  29.         if (!vals.count(cur))
  30.             vals[cur] = i;
  31.         cur = (cur * an) % m;
  32.     }
  33.  
  34.     for (ll i=0, cur=b; i<=n; ++i) {
  35.         if (vals.count(cur)) {
  36.             ll ans = vals[cur] * n - i;
  37.             if (ans < m)
  38.                 ans1 = min(ans,ans1);
  39.         }
  40.         cur = (cur * a) % m;
  41.     }
  42.     if(ans1 != 100*m)
  43.         return ans1;
  44.     else
  45.         return -1;
  46. }
  47. ll solve1 (ll a, ll b, ll m)
  48.  {
  49.     ll ans1 = 100*m;
  50.     ll n = (ll) sqrt (m + .0) + 1;
  51.  
  52.     ll an = 1;
  53.     for (ll i=0; i<n; ++i)
  54.         an = (an * a) % m;
  55.  
  56.     map<ll,ll> vals;
  57.     for (ll i=1, cur=an; i<=n; ++i) {
  58.         if (!vals.count(cur))
  59.             vals[cur] = i;
  60.         cur = (cur * an) % m;
  61.     }
  62.  
  63.     for (ll i=0, cur=b; i<=n; ++i) {
  64.         if (vals.count(cur)) {
  65.             ll ans = vals[cur] * n - i;
  66.             if (ans < m&&ans!=0LL)
  67.                 ans1 = min(ans,ans1);
  68.         }
  69.         cur = (cur * a) % m;
  70.     }
  71.     if(ans1 != 100*m)
  72.         return ans1;
  73.     else
  74.         return -1;
  75. }
  76. int main()
  77. {
  78.     int t,i;
  79.     scanf("%d",&t);
  80.     while(t--)
  81.     {
  82.         ll a,c,m,k;
  83.         scanf("%lld %lld %lld %lld",&a,&c,&m,&k);
  84.  
  85.         ll len=solve1(a,1LL,m);
  86.  
  87.         ll p=solve(a,c,m);
  88.  
  89.         if(p==-1)
  90.         {
  91.             printf("0\n");
  92.             continue;
  93.         }
  94.  
  95.         ll ans=(k*(k-1LL))/2LL;
  96.         ans%=mod;
  97.         ans=(ans*len)%mod;
  98.         ans=(ans+(k*p))%mod;
  99.         printf("%lld\n",ans);
  100.     }
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0s 4016KB
comments ()
stdin
copy 
1
15 4 221 1000
stdout
copy 
11990000
https://ideone.com/V75HGr
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!