codeforces 460B Little Dima and Equation 解题报告

题目链接：http://codeforces.com/problemset/problem/460/B

题目意思：给出a, b, c三个数，要你找出所有在 1 ≤ x ≤ 1e9 范围内满足 x = b·s(x)a + c 这条等式的x的个数，并输出相应的 x 具体是多少。

不看tutorial 都不知道，原来枚举的方向错了，人家是枚举1～81 的情况，我就是枚举1～1e9， = =。。。直接暴力即可，有个比较要注意的地方，算方程右边的时候有可能超过int，需要用long long 或 __int64 保存。

（1）long long 版

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 const int maxn = 1e6;   // 不知道符合的x有多少个，尽量开大一点吧

 const int maxx = 1e9;

 const int minx = ;

 typedef long long LL;

 int ans[maxn];

 LL tx;

 int main()

 {

     int a, b, c;

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

     {

         int cnt = ;

         for (int i = ; i <= ; i++)  // 枚举1～999999999每位数字和

         {

             int sx = i;

             int p = i;

             for (int j = ; j < a; j++)

                 sx *= p;

             tx = (LL)sx*b + (LL)c;

             if (tx > maxx || tx < minx)

                 continue;

             int x = sx*b + c;

             int tot = ;

             while (x)

             {

                 tot += x%;

                 x /= ;

             }

             if (tot == i)

                  ans[cnt++] = sx*b + c;

             }

         }

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

         for (int i = ; i < cnt; i++)

             printf("%d ", ans[i]);

     }

     return ;

 }

（2） __int64 版本

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 const int maxn = 1e6;

 const int maxx = 1e9;

 const int minx = ;

 int ans[maxn];

 __int64 tx, a, b, c;

 int main()

 {

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

     {

         int cnt = ;

         for (int i = ; i <= ; i++)  // 枚举1～999999999每位数字和

         {

             __int64 sx = i;

             __int64 p = i;

             for (int j = ; j < a; j++)

                 sx *= p;

             tx = sx*b + c;

             if (tx > maxx || tx < minx)

                 continue;

             __int64 x = sx*b + c;

             int tot = ;

             while (x)

             {

                 tot += x%;

                 x /= ;

             }

             if (tot == i)

                  ans[cnt++] = sx*b + c;

         }

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

         for (int i = ; i < cnt; i++)

             printf("%d ", ans[i]);

     }

     return ;

 }

总结：long long 写起来好像比 __int64 简单一些啦

这个是参考作者写的，本人更喜欢作者的写法，每个函数有各自的功能，而且比较清晰，很奇怪的是，用codeblocks 检验第三组数据 2 2 1 的时候，我的电脑一直输出0，用custom test 可以得出正确结果。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <vector>

 using namespace std;

 typedef long long ll;

 vector<ll> ans;

 ll a, b, c;

 ll S(ll p, ll a)

 {

     ll s = ;

     for (int i = ; i <= a; i++)

         s *= p;

     return s;

 }

 ll Digit(ll x)

 {

     ll wei = ;

     while (x)

     {

         wei += x % ;

         x /= ;

     }

     return wei;

 }

 int main()

 {

     int len = ;

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

     {

         for (ll i = ; i < len; i++)

             ans.clear();

         for (ll i = ; i <= ; i++)

         {

             ll x = b*S(i, a) + c;

             if (x < 1e9 && Digit(x) == i)

                 ans.push_back(x);

         }

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

         for (int i = ; i < ans.size(); i++)

             printf("%lld ", ans[i]);

         len = ans.size();

     }

     return ;

 }

巴特西

codeforces 460B Little Dima and Equation 解题报告

最新文章

热门文章