- 九星连珠
题目描述
当九星同时排列在太岁宫位置的之时，就是lester统治全宇宙之时。不过他不知道能不能活到那一天~~
共有n颗行星，行星i公转一圈需要mi年，最近一次达到太岁宫位置需要ai年。请问所有行星第一次全部位于太岁宫位置需要几年？
输入输出格式
输入格式
第一行一个正整数n 后面n行每行两个整数mi,ai
输出格式
如果无解，输出NO，否则输出一个正整数，表示答案
输入输出样例
输入样例#1:复 制
3 3 2 5 3 7 2
输出样例#1:复 制
23
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
说明
数据规模
10%的数据，n=1
另20%的数据，n=2
另30%的数据，n=3
所有数据中，有40%的数据mi两两互质
100%的数据，n<=9, 0<=ai<mi<=100，ai不会全部为0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll a[N],mod[N],ans,n,mulsum=1;
ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(!b)
{
x=1,y=0;
return a;
}
ll d=exgcd(b,a%b,x,y);
ll t=x;
x=y;y=t-a/b*y;
return d;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
n=read();
for(int i=1;i<=n;i++)mod[i]=read(),a[i]=read(),mulsum*=mod[i];
for(int i=1;i<=n;i++)
{
ll x,y;
ll mi=mulsum/mod[i];
exgcd(mi,mod[i],x,y);
x=((x%mod[i])+mod[i])%mod[i];
ans=(ans+(x*mi*a[i]))%mulsum;
}
cout<<ans<<"\n";
return 0;
}
知道哪里错了，但是不知道怎么改……
