异想天开

What's the true meaning of light, Could you tell me why

韩信点兵

日期:2015-05-15 22:14:32
  
最后更新日期:2015-05-20 17:46:35
http://acm.nyist.net/JudgeOnline/problem.php?pid=34
描述
相传韩信才智过人,从不直接清点自己军队的人数,只要让士兵先后以三人一排、五人一排、七人一排地变换队形,而他每次只掠一眼队伍的排尾就知道总人数了。输入3个非负整数a,b,c ,表示每种队形排尾的人数(a<3,b<5,c<7),输出总人数的最小值(或报告无解)。已知总人数不小于10,不超过100 。
输入
输入3个非负整数a,b,c ,表示每种队形排尾的人数(a<3,b<5,c<7)。例如,输入:2 4 5
输出
输出总人数的最小值(或报告无解,即输出No answer)。实例,输出:89
样例输入
2 1 6
样例输出
41
解析:
对于同余方程:
ax=b ( mod n)
有解的条件是 gcd(a,n)|b,即a,n的最大公约数,可以被b整除。
为什么是这样呢?可以这样想a为gcd(a,n)一个倍数,b若也为gcd(a,n)的一个倍数,而在模n内,gcd(a,n)的倍数是有限的,不断增加x的值
最终ax与b在模n的范围内会重复。
对于一般线性同余方程组可以用构造法构造出来:
x = c1 ( mod n1)
x = c2 ( mod n2)
x = c3 ( mod n3)
...
根据前面可以同余方程可以判断是否有解,若有解,则解的形式为:common=n1*n2*n3...,定义ti的求法:ti * common/ni = 1 ( mode ni),那么x的值可以表示为 ci * ti*common/ni的所有和,再与common求余。这题3,5,7为质数,gcd(a,n)为1,那么一定有解。
[code lang="cpp"]
#include<cstdio>
#include<cmath>
#include<cstdlib>

int a[3];
int s[3]={3,5,7};
int m[3]={5*7,3*7,3*5};

int sovle(){
scanf("%d %d %d",&a[0],&a[1],&a[2]);
int t[3];
int common=3*5*7,sum=0;
for (int i=0; i<3; ++i){
int tmp=m[i];
t[i]=1;
while ( tmp%s[i]!=1 ){
tmp += m[i];
t[i]++;
}
}

for (int i=0; i<3; ++i){
sum += (a[i]*m[i]*t[i])%common;
}
sum = sum%common;
if (sum<100 && sum>10){
printf("%d\n",sum);
} else {
printf("No answer\n");
}
return 0;
}

int main(){
sovle();
return 0;
}
[/code]