Codeforces 933 B. A Determined Cleanup（数学）

Codeforces 933 B. A Determined Cleanup（数学）

Description

In order to put away old things and welcome a fresh new year, a thorough cleaning of the house is a must.Little Tommy finds an old polynomial and cleaned it up by taking it modulo another. But now he regrets doing this…Given two integers p p and kk , find a polynomial f(x) f ( x ) with non-negative integer coefficients strictly less than k k , whose remainder is pp when divided by (x + k) ( x   +   k ) . That is, f(x) = q(x)⋅(x + k) + p f ( x )   =   q ( x ) · ( x   +   k )   +   p , where q(x) q ( x )

Input

The only line of input contains two space-separated integers p p and kk(1 ≤ p ≤ 1018,2 ≤ k ≤ 2 000) ( 1   ≤   p   ≤   10 18 , 2   ≤   k   ≤   2   000 )

Output

If the polynomial does not exist, print a single integer −1 − 1 In the first line print a non-negative integer d d In the second line print dd space-separated integers a0, a1, ..., ad − 1 a 0 ,   a 1 ,   . . . ,   a d   −   1 , describing a polynomial f(x)=∑d−1i=0ai⋅xi f ( x ) = ∑ i = 0 d − 1 a i · x i fulfilling the given requirements. Your output should satisfy 0 ≤ ai < k 0   ≤   a i   <   k for all 0 ≤ i ≤ d − 1 0   ≤   i   ≤   d   −   1 , and ad − 1 ≠ 0 a d   −   1   ≠   0 If there are many possible solutions, print any of them.

Examples input

46 2

Examples output

70 1 0 0 1 1 1

题意

给定正整数 p,k p , k ，我们需要找出一个多项式 q(x) q ( x ) ，使得 f(x) = q(x)⋅(x + k) + p f ( x )   =   q ( x ) · ( x   +   k )   +   p 的各项系数严格小于 k k 且不为负数，输出 f(x)f(x)

思路

仔细想想便可以知道，这样的解一定是存在的，所以没有输出 −1 − 1

我们可以对原式化简一下： f(x)=x⋅q(x)+k⋅q(x)+p f ( x ) = x · q ( x ) + k · q ( x ) + p

假设 q(x)=a1+a2⋅x+a3⋅x2+⋯+an⋅xn−1 q ( x ) = a 1 + a 2 · x + a 3 · x 2 + ⋯ + a n · x n − 1 ，其中 ai a i

现在我们再来讨论 f(x) f ( x )

常数项：k×a1+p k × a 1 + p一次项：k×a2+a1 k × a 2 + a 1二次项：k×a3+a2 k × a 3 + a 2…

于是我们有了一个通项不等式：0≤k×an+an−1

从上到下一一解出每一项即可，注意要保证系数不为负数

AC 代码

#include#define IO ios::sync_with_stdio(false);\ cin.tie(0);\ cout.tie(0);using namespace std;typedef __int64 LL;const int maxn = 1e5+10;LL a[maxn];LL ans[maxn];LL k,p;LL get(LL a1,int i){ ans[i] = ((a1 % k) + k) % k; return (ans[i] - a1)/k;}int main(){ IO; cin>>p>>k; a[0] = p; for(int i=1; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。