题目链接: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; }