fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define pb push_back
  6.  
  7. ll Extend_Euclidean(ll a , ll b , ll &x , ll &y)
  8. {
  9. 	if(b==0) {
  10. 		x=1;
  11. 		y=0;
  12. 		return a;
  13. 	}
  14.  
  15. 	ll x1,y1;
  16. 	ll g=Extend_Euclidean(b,a%b,x1,y1);
  17. 	x=y1;
  18. 	y=x1-y1*(a/b);
  19. 	return g;
  20. }
  21.  
  22. signed main()
  23. {
  24.   ios_base::sync_with_stdio(false);
  25.   cin.tie(NULL);
  26.   cout.tie(NULL);
  27.  
  28.   ll t;
  29.   cin>>t;
  30.  
  31.   while(t--)
  32.   {
  33.      vector<pair<ll,ll>> input;
  34.  
  35.      ll n, lcm=1,result=0;
  36.      cin >> n;
  37.  
  38.       for(ll i=0;i<n;i++)
  39.       {
  40.       	 ll a , m;
  41.       	 cin >> m >> a;
  42.  
  43.          lcm *= m;
  44.  
  45.         input.pb({m,a});
  46.       }
  47.  
  48.       for(ll i=0;i<n;i++)
  49.       {
  50.       	ll M = lcm/input[i].first;
  51.       	ll k, y;
  52.         ll g=Extend_Euclidean(M,input[i].first,y,k);
  53.         if(g!=1) {cout<<"NO SOLUTION"<<"\n";break;}
  54.  
  55.       	y = ( y % input[i].first + input[i].first ) % input[i].first;
  56.  
  57.         result += M * y * input[i].second % lcm;
  58.  
  59.       }
  60.  
  61.       cout<<result % lcm<<"\n" ;
  62.  
  63.  
  64.  
  65.   }
  66.   return 0;
  67. }
Runtime error #stdin #stdout 1.82s 2095556KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7k9A0H
language:
C++14 (gcc 8.3)
created:
2 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!