這道題我第一眼居然想著用二分法做，結果，還是不滿足二分條件，
WA代碼如下
#include<iostream>
using namespace std;
const int N=30;
int a[N],m[N];
int n;
bool check(int x)
{
for(int i=1;i<=n;i++)
{
if(x%a[i]!=m[i])
return false;
}
return true;
}
int main(void)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&m[i]);
}
int l=1,r=1e9;
while(l<r)
{
int mid=l+r>>1;
if(check(mid)) r=mid;
else
l=mid+1;
}
if(check(l))
printf("%d",l);
else
printf("-1");
}
我找到了一個很優質的題解轉載自一位大佬
https://www.acwing.com/solution/content/21747/
這個題解寫的很詳細，和y總說的很一致，
我看y總視頻看明白了用歐幾里得求k1,之后就卡住了，看了這篇博文，我好像也是明白了很多，
給大家看看博文的核心內容
除了最后一步的a1,m1更新操作沒看懂，其余的我可以寫出大致思路，
代碼如下
剛開始我覺得代碼應該是這樣的，但是發現WA了，應該是爆堆疊了，所以看了一下別的代碼，我發現他們多了一步很關鍵的操作
錯誤代碼如下，
#include<iostream>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1,y=0;
return a;
}
LL d;
d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main(void)
{
int n;
scanf("%d",&n);
LL a1,m1;
cin>>a1>>m1;
bool flag=true;
for(int i=0;i<n-1;i++)
{
LL a2,m2;
cin>>a2>>m2;
LL k1,k2;
LL d=exgcd(a1,-a2,k1,k2);
if((m2-m1)%d)
{flag=false;
break;}
k1*=(m2-m1)/d;
LL t=a2/d;
m1=k1*a1+m1;
a1=abs(a1/d*a2);
}
if(flag) printf("%lld",(m1%a1+a1)%a1);
else
puts("-1");
}
k1=(k1%t+t)%t
這一步很類似于哈希，可能是為了防止后面的遞推被錯誤認為不能執行然后被誤判為不能得到x.
其實 這樣可以有效避免了誤判，
圖例如下
#include<iostream>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1,y=0;
return a;
}
LL d;
d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main(void)
{
int n;
scanf("%d",&n);
LL a1,m1;
cin>>a1>>m1;
bool flag=true;
for(int i=0;i<n-1;i++)
{
LL a2,m2;
cin>>a2>>m2;
LL k1,k2;
LL d=exgcd(a1,-a2,k1,k2);
if((m2-m1)%d)
{flag=false;
break;}
k1*=(m2-m1)/d;
LL t=a2/d;
k1=(k1%t+t)%t;
m1=k1*a1+m1;
a1=abs(a1/d*a2);
}
if(flag) printf("%lld",(m1%a1+a1)%a1);
else
puts("-1");
}
很神奇，
又是Orz的一天！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261856.html
標籤：其他