CodeForces 460B

Little Dima and Equation

Time Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Submit Status Practice CodeForces 460B

Description

Little Dima misbehaved during a math lesson a lot and the nasty teacher Mr. Pickles gave him the following problem as a punishment.

Find all integer solutions x (0 < x < 109) of the equation:

x = b·s(x)a + c, 

where abc are some predetermined constant values and function s(x) determines the sum of all digits in the decimal representation of number x.

The teacher gives this problem to Dima for each lesson. He changes only the parameters of the equation: abc. Dima got sick of getting bad marks and he asks you to help him solve this challenging problem.

Input

The first line contains three space-separated integers: a, b, c (1 ≤ a ≤ 5; 1 ≤ b ≤ 10000;  - 10000 ≤ c ≤ 10000).

Output

Print integer n — the number of the solutions that you‘ve found. Next print n integers in the increasing order — the solutions of the given equation. Print only integer solutions that are larger than zero and strictly less than 109.

Sample Input

Input

3 2 8

Output

310 2008 13726 

Input

1 2 -18

Output

0

Input

2 2 -1

Output

41 31 337 967 

枚举s(x),最大为81
 1 //2016.8.2
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <vector>
 5
 6 using namespace std;
 7
 8 int S(int x)
 9 {
10     int ans = 0;
11     while(x)
12     {
13         ans += x%10;
14         x /= 10;
15     }
16     return ans;
17 }
18
19 long long pow(int a, int b)
20 {
21     long long ans = 1;
22     while(b--)
23     {
24         ans *= a;
25     }
26     return ans;
27 }
28
29 int main()
30 {
31     int a, b, c;
32     long long x;
33     while(scanf("%d%d%d", &a, &b, &c)!=EOF)
34     {
35         vector<long long> v;
36         for(int i = 1; i <= 81; i++)
37         {
38             x = b*pow(i, a)+c;
39             if(x >= 1000000000 || x < 0)continue;
40             if(S(x)==i)v.push_back(x);
41         }
42         cout << v.size()<<endl;
43         if(!v.empty())
44             for(vector<long long>::iterator it = v.begin(); it != v.end(); it++)
45                 if(it == v.begin())cout<<*it;
46                 else cout << " " << *it;
47           cout << endl;
48     }
49     return 0;
50 }
时间: 08-08

CodeForces 460B的相关文章

Codeforces Round #262 (Div. 2) 460B. Little Dima and Equation(枚举)

题目链接:http://codeforces.com/problemset/problem/460/B B. Little Dima and Equation time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Little Dima misbehaved during a math lesson a lot and the nas

Codeforces Round #262 (Div. 2) (460A 460B 460C 460D)

460A Vasya and Socks 题意:n个物品每天用一个  m天得一个  问  最多连续用几天 思路: 没思路-  就是暴力- 代码: #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<algorithm> #include<cmath> #include<map> #include<set>

【codeforces 718E】E. Matvey&#39;s Birthday

题目大意&链接: http://codeforces.com/problemset/problem/718/E 给一个长为n(n<=100 000)的只包含‘a’~‘h’8个字符的字符串s.两个位置i,j(i!=j)存在一条边,当且仅当|i-j|==1或s[i]==s[j].求这个无向图的直径,以及直径数量. 题解:  命题1:任意位置之间距离不会大于15. 证明:对于任意两个位置i,j之间,其所经过每种字符不会超过2个(因为相同字符会连边),所以i,j经过节点至多为16,也就意味着边数至多

Codeforces 124A - The number of positions

题目链接:http://codeforces.com/problemset/problem/124/A Petr stands in line of n people, but he doesn't know exactly which position he occupies. He can say that there are no less than a people standing in front of him and no more than b people standing b

Codeforces 841D Leha and another game about graph - 差分

Leha plays a computer game, where is on each level is given a connected graph with n vertices and m edges. Graph can contain multiple edges, but can not contain self loops. Each vertex has an integer di, which can be equal to 0, 1 or  - 1. To pass th

Codeforces Round #286 (Div. 1) A. Mr. Kitayuta, the Treasure Hunter DP

链接: http://codeforces.com/problemset/problem/506/A 题意: 给出30000个岛,有n个宝石分布在上面,第一步到d位置,每次走的距离与上一步的差距不大于1,问走完一路最多捡到多少块宝石. 题解: 容易想到DP,dp[i][j]表示到达 i 处,现在步长为 j 时最多收集到的财富,转移也不难,cnt[i]表示 i 处的财富. dp[i+step-1] = max(dp[i+step-1],dp[i][j]+cnt[i+step+1]) dp[i+st

Codeforces 772A Voltage Keepsake - 二分答案

You have n devices that you want to use simultaneously. The i-th device uses ai units of power per second. This usage is continuous. That is, in λ seconds, the device will use λ·ai units of power. The i-th device currently has bi units of power store

Educational Codeforces Round 21 G. Anthem of Berland(dp+kmp)

题目链接:Educational Codeforces Round 21 G. Anthem of Berland 题意: 给你两个字符串,第一个字符串包含问号,问号可以变成任意字符串. 问你第一个字符串最多包含多少个第二个字符串. 题解: 考虑dp[i][j],表示当前考虑到第一个串的第i位,已经匹配到第二个字符串的第j位. 这样的话复杂度为26*n*m*O(fail). fail可以用kmp进行预处理,将26个字母全部处理出来,这样复杂度就变成了26*n*m. 状态转移看代码(就是一个kmp

Codeforces Round #408 (Div. 2) B

Description Zane the wizard is going to perform a magic show shuffling the cups. There are n cups, numbered from 1 to n, placed along the x-axis on a table that has m holes on it. More precisely, cup i is on the table at the position x?=?i. The probl