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 。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

     int a, b;

     while (scanf("%d%d", &a, &b) != EOF)

     {

         int ans = ;

         int mul = a - b;

         if (mul == )

             printf("infinity\n");

         else

         {

             bool flag = false;

             for (int i = ; i*i <= mul; i++)

             {

                 if (mul % i == )

                 {

                     if (i > b)

                         ans++;

                     if (mul/i > b && mul/i != i)   // 注意

                         ans++;

                 }

             }

             printf("%d\n", ans);

         }

     }

     return ;

 }

巴特西

codeforces 495B. Modular Equations 解题报告

最新文章

热门文章