题目描述
这是一道构造题.
诗乃在心中想了一个 n+1 项的多项式 f(x). 第 i 项的次数为 i, 系数为 ai:
f(x)=a0?+a1?*x+a2?*x2+a3?*x3+?+an*?xn
给定 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)≤1018.
所有数据的时间限制为 1000ms, 空间限制为 256MB, 可开启 O2 优化.
题解
这是一道数学题.
在输入完后, 我们先预处理处≤f(m)的所有 m 的次方, 然后以次计算 a0 到 an(n 为≤f(m)的 m 的次方的最大指数), 注意 a0 到 an 都不能≥m, 开 long long!!!
最后, 特判一下 m>f(m)的情况就可以 AC 啦!
附 AC 代码:
- #include <bits/stdc++.h> // 万能头文件
- #define int long long // 把 int 都定义成 long long
- using namespace std; // 使用标准名字空间
- inline int read() // 快速读入
- {
- int f = 1, x = 0;
- char c = getchar();
- while (c <'0' || c> '9')
- {
- if (c == '-')
- f = -1;
- c = getchar();
- }
- while (c>= '0' && c <= '9')
- {
- x = x * 10 + c - '0';
- c = getchar();
- }
- return f * x;
- }
- int n, m, a[105], fm, S = 1, s[105], cnt = -1;
- signed main() // 注意不能用 int main(), 因为我们已经在一开始把 int 都转换成了 long long
- {
- m = read(), fm = read(); // 读入 m 和 f(m)
- if (m> fm) // 特判 m>f(m)的情况
- {
- printf("1\n%lld", fm); // 直接输出 1 和 f(m)
- return 0;
- }
- while (true) // 预处理处所有≤f(m)的 m 的次方
- {
- if (S> fm) // 如果已经比 f(m)大了
- {
- break; // 就退出
- }
- else
- {
- s[++cnt] = S; // 否则记录下这个数
- S = S * m; // 将它 * m
- }
- }
- int b = fm; //b 为 f(m)的复制品
- a[++n] = fm % m; // 预处理处 a0(常数项)
- b = b - fm % m; // 减去常数项
- for (register int i = 1; i <= cnt; i++)
- {
- a[++n] = (b / s[i]) % m; // 依次计算每一位
- }
- printf("%lld\n", n); // 输出 n
- for (register int i = 1; i <= n; i++)
- {
- printf("%lld", a[i]); // 输出 a[i]
- }
- return 0; // 结束
- }
来源: http://www.bubuko.com/infodetail-2983057.html