850
HDU1573 一元線性同餘方程組
這題很水啊 就是求解一元線性方程組的解 然後問在n的範圍內解的個數 很正常的一道題
竟然在輸入上 WA了無數次 這個就有點慘了 這個同餘方程的解是按照最小公倍數的往上
循環的 然後再注意一下求出的解為0的邊界問題就可以了
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
void exgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
if(b==0)
{
x=1,y=0,d=a;
return;
}
exgcd(b,a%b,d,x,y);
long long temp=x;
x=y;
y=temp-(a/b)*y;
}
long long gcd(long long a,long long b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
int main()
{
long long a[15],b[15],m,n,t,a1,r1,a2,r2,c,d,x,y,gc,a0,b0;
cin>>t;
while(t--)
{
bool flag=0;
gc=1;
cin>>n>>m;
for(int i=0; i<m; i++)
cin>>b[i],gc=gc/gcd(gc,b[i])*b[i];
for(int i=0; i<m; i++)
cin>>a[i];
r1=a[0];
a1=b[0];
for(int i=1; i<m; i++)
{
a2=b[i],r2=a[i];
a0=a1,b0=a2,c=r2-r1;
exgcd(a0,b0,d,x,y);
if(c%d)
{
flag=1;
break;
}
long long t=b0/d;
x=(x*(c/d)%t+t)%t;
r1=r1+a1*x;
a1=a1*(a2/d);
}
if(flag)
{
printf("0\n");
continue;
}
long long ans=0;
if(r1<=n)
ans=1+(n-r1)/gc;
if(ans&&r1==0)
ans--;
printf("%lld\n",ans);
}
return 0;
}
最後更新：2017-04-04 07:03:34