第一行一个整数ni
之后有n行，第i+1行有两个整数a
,bi
，表示
设答案为
，你只需要找到一个最小的非负整数T，使得
输出这个T就行了
数据范围5
0 ≤ n ≤ 10
i
1 ≤ a
≤ bi
≤ 105
1 // 扩展欧几里得做法； 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cstring> 6 #define ll long long 7 using namespace std; 8 9 ll ex_gcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得（扩展gcd） 10 { 11 if (a==0&&b==0) return -1; 12 if (b==0){x=1;y=0;return a;} 13 ll d=ex_gcd(b,a%b,y,x); 14 y-=a/b*x; 15 return d; 16 } 17 18 ll mod_inverse(ll a,ll mod)//乘法逆元 19 { 20 ll x,y; 21 ll d = ex_gcd(a,mod,x,y); 22 return (x%mod+mod)%mod; 23 } 24 int low_bit(int x){return x&(-x);} 25 int main() 26 { 27 for(int i=0;i<=16;i++) 28 cout<<i<<‘ ‘<<low_bit(i)<<endl; 29 return 0; 30 }
解题代码如下：
1 #include<iostream> 2 using namespace std; 3 #define ll long long 4 ll ex_gcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得（扩展gcd） 5 { 6 if (a==0&&b==0) return -1; 7 if (b==0){x=1;y=0;return a;} 8 ll d=ex_gcd(b,a%b,y,x); 9 y-=a/b*x; 10 return d; 11 } 12 13 ll mod_inverse(ll a,ll mod)//乘法逆元 14 { 15 ll x,y; 16 ll d = ex_gcd(a,mod,x,y); 17 return (x%mod+mod)%mod; 18 } 19 long long gcd(long long a,long long b) 20 { 21 long long c=1; 22 while(c) 23 { 24 c=a%b; 25 a=b; 26 b=c; 27 } 28 return a; 29 } 30 int main() 31 { 32 int n; 33 cin>>n; 34 long long a,b,c,sum_a=1,sum_b=1; 35 for(int i=0;i<n;i++) 36 { 37 cin>>a>>b; 38 c=gcd(a,b); 39 a/=c; 40 b/=c; 41 sum_a*=b-a; 42 sum_b*=b; 43 sum_b%=1000000007; 44 sum_a%=1000000007; 45 } 46 c=gcd(sum_a,sum_b); 47 sum_a/=c; 48 sum_b/=c; 49 sum_a=(sum_b-sum_a+1000000007)%10000000007; 50 c=mod_inverse(sum_b,1000000007); 51 cout<<c*sum_a%1000000007; 52 }
原文：https://www.cnblogs.com/lu1nacy/p/10013853.html