X問題(中国残余定理+非互質版応用)hdu 1573
6610 ワード
X問題
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3921 Accepted Submission(s): 1253
Problem Description
N以下の正の整数の中でどれだけのXが満たすことを求めます:X mod a[0]=b[0],X mod a[1]=b[1],X mod a[2]=b[2],…,X mod a[i]=b[i],…(0
Input
入力データの第1の挙動は、T組のテストデータがあることを示す正の整数Tである.各試験データの第1の挙動の2つの正の整数N,M(0
Output
各入力セットに対応して、条件を満たすXの個数を表す正の整数が独立した行に出力される.
Sample Input
3
10 3
1 2 3
0 1 2
100 7
3 4 5 6 7 8 9
1 2 3 4 5 6 7
10000 10
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9
Sample Output
1
0
3
応用の下で、さっき学んだ中国の残りの定理(非互質版);題意はもう言わないで、中国語の.
転載は出典を明記してください:http://www.cnblogs.com/yuyixingkong/
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1573
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3921 Accepted Submission(s): 1253
Problem Description
N以下の正の整数の中でどれだけのXが満たすことを求めます:X mod a[0]=b[0],X mod a[1]=b[1],X mod a[2]=b[2],…,X mod a[i]=b[i],…(0
Input
入力データの第1の挙動は、T組のテストデータがあることを示す正の整数Tである.各試験データの第1の挙動の2つの正の整数N,M(0
Output
各入力セットに対応して、条件を満たすXの個数を表す正の整数が独立した行に出力される.
Sample Input
3
10 3
1 2 3
0 1 2
100 7
3 4 5 6 7 8 9
1 2 3 4 5 6 7
10000 10
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9
Sample Output
1
0
3
応用の下で、さっき学んだ中国の残りの定理(非互質版);題意はもう言わないで、中国語の.
転載は出典を明記してください:http://www.cnblogs.com/yuyixingkong/
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1573
#include<stdio.h>
#define LL __int64
LL A[15],B[15];
LL d,x,y,ans;
LL dg;//
void exgcd(LL a,LL b,LL& d,LL& x,LL& y)
{
if(!b){d=a;x=1;y=0;}
else
{
exgcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
LL gcd(LL a,LL b)
{
if(!b) return a;
else
gcd(b,a%b);
}
LL China(LL n)
{
LL dm,a,b,d,x,y;
LL c1,c2,c;
a=A[0];
c1=B[0];
for(int i=1;i<n;i++)
{
b=A[i];
c2=B[i];
exgcd(a,b,d,x,y);
dm=b/d;
c=c2-c1;
if(c%d) return -1;
x=((x*c/d)%dm+dm)%dm;
c1=a*x+c1;
a=a*b/d;
}
dg=a;
if(c1==0)
{
c1=1;
for(int i=0;i<n;i++)
{
c1=c1*A[i]/gcd(c1,A[i]);
}
dg=c1;
}
return c1;
}
int main()
{
LL T,N,M;
scanf("%I64d",&T);
while(T--)
{
scanf("%I64d%I64d",&N,&M);
for(LL i=0;i<M;i++) scanf("%I64d",&A[i]);
for(LL i=0;i<M;i++) scanf("%I64d",&B[i]);
ans=China(M);
//printf("ans==%I64d\tdg=%I64d
",ans,dg);
if(ans==-1||ans>N) printf("0
");
else
{
printf("%I64d
",(N-ans)/dg+1);
}
}
return 0;
}