fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=1000+10;
  27.  
  28. int n;
  29. int a[MAX],b[MAX];
  30.  
  31. LL extend_gcd(LL a,LL b,LL& nx,LL& ny)
  32. {
  33. 	if(!b)
  34. 	{
  35. 		nx=(a>0?1:-1);
  36. 		ny=0;
  37. 		return a;
  38. 	}
  39. 	LL tx,ty;
  40. 	LL d=extend_gcd(b,a%b,tx,ty);
  41. 	nx=ty;
  42. 	ny=tx-(a/b)*ty;
  43. 	return d;
  44. }
  45.  
  46. void Merge(LL a1,LL b1,LL a2,LL b2,LL& x,LL& y,LL& z)
  47. {
  48. 	LL B=__gcd(b1,b2);
  49. 	b1/=B;
  50. 	b2/=B;
  51.  
  52. 	LL tx,ty;
  53. 	z=extend_gcd(b1,b2,tx,ty)*B;
  54. 	x=a1*tx+a2*ty;
  55. 	y=a1*b2-a2*b1;
  56. }
  57.  
  58. void Merge(LL& x,LL& z,LL& y,LL nx,LL ny)
  59. {
  60. 	LL tx,tz,ty;
  61. 	Merge(x,z,nx,ny,tx,ty,tz);
  62. 	LL g=__gcd(y,ty);
  63. 	x=tx;
  64. 	z=tz;
  65. 	y=g;
  66. }
  67.  
  68. int main()
  69. {
  70. //	freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  71. 	int i;
  72. 	scanf("%d",&n);
  73. 	REP(i,1,n)
  74. 		scanf("%d%d",&a[i],&b[i]);
  75. 	LL x,y,z;
  76. 	Merge(a[1],b[1],a[2],b[2],x,y,z);
  77. 	REP(i,3,n)
  78. 		Merge(x,z,y,a[i],b[i]);
  79. 	while(x<-10000)
  80. 		x+=abs(y);
  81. 	while(x>10000)
  82. 		x-=abs(y);
  83. 	cout<<x<<" "<<z<<endl;
  84. 	cout<<y<<" "<<0<<endl;
  85. 	return 0;
  86. }
  87.  
Runtime error #stdin #stdout 0s 3352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8gI7sw
language:
C++ (gcc 8.3)
created:
10 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!