# Codeforces 933 B. A Determined Cleanup（数学）

xiaoxiao2021-02-28  100

## 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 ) is a polynomial (not necessarily with integer coefficients).

## Input

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

## Output

If the polynomial does not exist, print a single integer 1 − 1 , or output two lines otherwise.

In the first line print a non-negative integer d d — the number of coefficients in the polynomial.

In the second line print dd space-separated integers a0,a1,...,ad1 a 0 ,   a 1 ,   . . . ,   a d   −   1 , describing a polynomial f(x)=d1i=0aixi f ( x ) = ∑ i = 0 d − 1 a i · x i fulfilling the given requirements. Your output should satisfy 0ai<k 0   ≤   a i   <   k for all 0id1 0   ≤   i   ≤   d   −   1 , and ad10 a d   −   1   ≠   0 .

If there are many possible solutions, print any of them.

46 2

7 0 1 0 0 1 1 1

## AC 代码

#include<bits/stdc++.h> #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<maxn; i++) { a[i] = get(a[i-1],i); if(!a[i]) { cout<<i<<endl; for(int j=1; j<=i; j++) cout<<ans[j]<<" "; cout<<endl; break; } } return 0; }