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.

 

Examples input

46 2

 

Examples output

7 0 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)=xq(x)+kq(x)+p f ( x ) = x · q ( x ) + k · q ( x ) + p

假设 q(x)=a1+a2x+a3x2++anxn1 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

于是我们有了一个通项不等式: 0k×an+an1<k 0 ≤ k × a n + a n − 1 < k ,其中 a0=p a 0 = p

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

 

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; }
转载请注明原文地址: https://www.6miu.com/read-2600050.html

最新回复(0)