fork download
copy 
  1. // author : anphung
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define con_meo_dua_leo int32_t main
  5. #define int64 long long
  6. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  7. #define f0(i, a, b) for(int i = (a); i <=(b); ++i)
  8. #define fd(i, a, b) for(int i = (a); i >=(b); --i)
  9. #define file ""
  10.  
  11. //mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
  12.  
  13. //int64 Rand(int64 l, int64 r){
  14. //    return l+rng()%(r-l+1);
  15. //}
  16.  
  17. #define maxn 1
  18. #define lg 20
  19. #define inf (int64)4e18
  20. #define mod (int64)(1e9+7)
  21.  
  22.  
  23. long long n, p, a, b, r;
  24.  
  25. inline long long gcd(long long a, long long b){
  26.     if(b == 0)return a;
  27.     return gcd(b, a%b);
  28. }
  29.  
  30. inline long long add(long long a, long long b, long long p){
  31.     return (a%p + b%p)%p;
  32. }
  33.  
  34. con_meo_dua_leo(){
  35.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  36.     // freopen(file".inp", "r", stdin);
  37.     // freopen(file".out", "w", stdout);
  38.  
  39.     cin>>n>>p>>a>>b>>r;
  40.     long long s = (r - (n%p)+p)%p;
  41.  
  42.     long long g = gcd(gcd(a, b), p);
  43.     if(s%g != 0){
  44.         return cout<<-1, 0;
  45.     }
  46.  
  47.     long long p2 = p/g;
  48.     long long a2 = a/g;
  49.     long long b2 = b/g;
  50.     long long s2 = s/g; 
  51.  
  52.     vector<int> d(p2, -1);
  53.     queue<int> q;
  54.  
  55.     d[0] = 0; q.push(0);
  56.  
  57.     while(!q.empty()){
  58.         int u = q.front(); q.pop();
  59.  
  60.         int v1 = (u + a2) % p2;
  61.         int v2 = (u + b2) % p2;
  62.         int v3 = (u + a2 + b2) % p2;
  63.  
  64.         if(d[v1] == -1){
  65.             d[v1] = d[u] + 1;
  66.             q.push(v1);
  67.         }
  68.         if(d[v2] == -1){
  69.             d[v2] = d[u] + 1;
  70.             q.push(v2);
  71.         }
  72.         if(d[v3] == -1){
  73.             d[v3] = d[u] + 1;
  74.             q.push(v3);
  75.         }
  76.     }
  77.  
  78.  
  79.     cout<<d[s2];
  80.  
  81.     cerr << "\ntime elapsed: "<<TIME <<"s.\n";
  82. }
  83.  
Success #stdin #stdout #stderr 0.01s 5312KB
comments (?)
stdin
copy 
20 16
3 4 15
stdout
copy 
2
stderr
copy 
time elapsed: 0.0065s.
https://ideone.com/TT3cgP
language:
C++14 (gcc 8.3)
created:
4 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!