现在的位置: 首页 > 综合 > 正文

NYOJ-34 韩信点兵【数论】

2013年10月27日 ⁄ 综合 ⁄ 共 729字 ⁄ 字号 评论关闭

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=34

解题思路:

刚开始学算法时候写的这道题,因为数据比较小,从10到100,所以当时是暴力枚举的。

昨天看到了正确的解法:

原理:

1.因为这个数能被5和7整除而不能被3整除,所以肯定是5和7的倍数,也就是35k,但是我们需要保证被3除的结果是a,所以我们令k=2,这样,70k%3=1,而k=1时,35k%3=2,所以,能被5和7整除不能被3整除且余数为a的数为70a。

2.被3和7整除,不能被5整除,则为21k,k=1时,正好余1,所以这个数为21b。

3.被3和5整除,不能被7整除,则为15k,k=1时,正好余1,所以这个数为15c。

所以,这个数为70a+21b+15c,又因为3、5、7的最小公倍数为105,所以这个数肯定在0到105以内,所以对结果取余一下即可。

推广到其他情况也是同样道理。

比如,求除以5、7、11以后所得余数为a,b,c.则这个数是:231a+330b+210c,然后对5×7×11=385取余即可。

代码如下:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;

int main()
{
	int a, b, c;
	while(scanf("%d %d %d", &a, &b, &c) != EOF)
	{
		int ans = (70 * a + 21 * b + 15 * c ) % 105;
		if(ans < 10 || ans > 100)
			printf("No answer\n");
		else
			printf("%d\n", ans);
	}
	return 0;
}

抱歉!评论已关闭.