k-rounding
For a given positive integer n denote its k-rounding as the minimum positive integer x, such that x ends with k or more zeros in base 10 and is divisible by n.
For example, 4-rounding of 375 is 375·80 = 30000. 30000 is the minimum integer such that it ends with 4 or more zeros and is divisible by 375.
Write a program that will perform the k-rounding of n.
Input
The only line contains two integers n and k (1 ≤ n ≤ 109, 0 ≤ k ≤ 8).
Output
Print the k-rounding of n.
Examples
Input
375 4 Output
30000 Input
10000 1 Output
10000 Input
38101 0 Output
38101 Input
123456789 8 Output
12345678900000000
题意，找一个最小的x，使满足n*x%(10^k)==0,即n*x==(10^k)*y,也即n*x===0(mod (10^k))
可以用ex_gcd来解方程，过程是：先求出n*x+（10^k）*y==gcd（n，10^k）的解，再乘0/gcd就是方程的一个特解（其实不用ex_gcd，因为特解一定是（0，0））。然后求大于0的最小x，即0+1*（10^k）/gcd(n,10^k),n*x=lcm(n,10^k)
或者利用唯一分解定理，把n和10^k分解为若干素数的乘积，可以想象，要使n*x模10^k等于0，那么n*x就是lcm(n,10^k)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k;
ll fac(ll x)
{
ll ret=1;
while(x--)ret*=10;
return ret;
}
int main()
{
cin>>n>>k;
cout<<fac(k)/__gcd(n,fac(k))*n<<endl;
return 0;
}
