首页 > 代码库 > codeforces 495B. Modular Equations 解题报告
codeforces 495B. Modular Equations 解题报告
题目链接：http://codeforces.com/problemset/problem/495/B
题目意思：给出两个非负整数a，b，求出符合这个等式 
的所有x，并输出 x 的数量，如果 x 有无限多个，那么输出 infinity。
想了半个多小时......有个地方想遗漏了。
a mod x == b，等价于 a = k*x + b。设 mul = a - b，那么 k*x = mul，然后就不断枚举 mul 的因子，即 kx = mul。由于 mod 出来的结果为 b，那么 k 或 x 至少有一个比 b 大。
/***************************************
我没有想出来的地方是，求出来两个因子 i、mul/i 只保留大的那个，然后跟 b 比较，大于的话统计个数（累计一次）。但是没有想到 i 和 mul/i 可能两个都比 b 大，那么此时应该是累计两次！
****************************************/
还有一些需要注意的地方，因为 a，b最大可能达到 1e9，枚举因子的时候，平方根以内枚举即可。最后就是输出 infinity 的情况，就是 a = b，根据样例看出来的。此时 kx = 0 。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 int main() 9 {10 #ifndef ONLINE_JUDGE11 freopen("in.txt", "r", stdin);12 #endif // ONLINE_JUDGE13 int a, b;14 while (scanf("%d%d", &a, &b) != EOF)15 {16 int ans = 0;17 int mul = a - b;18 if (mul == 0)19 printf("infinity\n");20 else21 {22 bool flag = false;23 for (int i = 1; i*i <= mul; i++)24 {25 if (mul % i == 0)26 {27 if (i > b)28 ans++;29 if (mul/i > b && mul/i != i) // 注意30 ans++;31 }32 }33 printf("%d\n", ans);34 }35 }36 return 0;37 }
codeforces 495B. Modular Equations 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。