题目描述

这是一道构造题。

诗乃在心中想了一个n+1项的多项式f(x)。第i项的次数为i，系数为ai：

　　f(x)=a0​+a1​*x+a2​*x²+a3​*x³+⋯+an*​xⁿ

给定m以及f(m)的值（即当x=m时此多项式的值），请构造多项式，满足任意0≤ai<m且ai为非负整数。

设你构造的多项式项数为n，则必须满足1≤n≤100且最高项系数不为零。

输入输出格式

输入格式：

两个整数，m、f(m)。

输出格式：

第一行输出正整数n，表示多项式的项数。

第二行依次输出n个非负整数（a[0]至a[n-1]），每个非负整数之间用一个空格隔开。

输入输出样例

输入样例#1： 

10 10

输出样例#1：

2
0 1

说明

对于20%的数据， 2≤m≤5.

对于100%的数据， 2≤m,f(m)≤10¹⁸.

所有数据的时间限制为 1000ms，空间限制为 256MB，可开启O2优化。

题解

这是一道数学题。

在输入完后，我们先预处理处≤f(m)的所有m的次方，然后以次计算a0到an（n为≤f(m)的m的次方的最大指数），注意a0到an都不能≥m,开long long！！！

最后，特判一下m>f(m)的情况就可以AC啦！

附AC代码：

 1 #include <bits/stdc++.h> //万能头文件
 2 #define int long long    //把int都定义成 long long
 3 
 4 using namespace std; //使用标准名字空间
 5 
 6 inline int read() //快速读入
 7 {
 8     int f = 1, x = 0;
 9     char c = getchar();
10 
11     while (c < '0' || c > '9')
12     {
13         if (c == '-')
14             f = -1;
15         c = getchar();
16     }
17 
18     while (c >= '0' && c <= '9')
19     {
20         x = x * 10 + c - '0';
21         c = getchar();
22     }
23 
24     return f * x;
25 }
26 
27 int n, m, a[105], fm, S = 1, s[105], cnt = -1;
28 
29 signed main() //注意不能用int main()，因为我们已经在一开始把int都转换成了long long
30 {
31     m = read(), fm = read(); //读入m和f(m)
32 
33     if (m > fm) //特判m>f(m)的情况
34     {
35         printf("1\n%lld", fm); //直接输出1和f(m)
36 
37         return 0;
38     }
39 
40     while (true) //预处理处所有≤f(m)的m的次方
41     {
42         if (S > fm) //如果已经比f(m)大了
43         {
44             break; //就退出
45         }
46         else
47         {
48             s[++cnt] = S; //否则记录下这个数
49 
50             S = S * m; //将它*m
51         }
52     }
53 
54     int b = fm; //b为f(m)的复制品
55 
56     a[++n] = fm % m; //预处理处a0(常数项)
57 
58     b = b - fm % m; //减去常数项
59 
60     for (register int i = 1; i <= cnt; i++)
61     {
62         a[++n] = (b / s[i]) % m; //依次计算每一位
63     }
64 
65     printf("%lld\n", n); //输出n
66 
67     for (register int i = 1; i <= n; i++)
68     {
69         printf("%lld ", a[i]); //输出a[i]
70     }
71 
72     return 0; //结束
73 }