题目描述

牛牛上二年级了，他正在学习乘法。 老师在课上介绍乘法的性质：两个非零数字相乘不会得到零。 但是牛牛并不赞同，他说：“$2$乘以$5$等于$10$，$10$的个位不就是零吗，我得到零了！” 老师刚想批评牛牛，没想到牛牛反将一军：“得到一个零太简单了，我想要得到𝑘个零。现在给你一个数字𝑎,你需要找到一个最小的正整数𝑏,使得𝑎∗𝑏的末尾至少有𝑘个零。” 老师发现原来自己也不会乘法，于是被气哭，他找到了你来挽回尊严，你能帮助他吗？

分析: 这道题可以这么想:我想让b尽可能小,就要让$a$尽可能大。 a最多可以贡献$10^k/x$($x>0$)，我们根据这个可以推导出$x=10^k/a(x>0)$，也就是$x=gcd(10^k,a)$。(其实你们因该知道,$x$其实就是我要找的$b$)这里$a$最大是10^18,注意开long long。

错因:最开始我直接用暴力枚举,却没看到数据范围,结果超时了,只拿20分。

代码:

#include<bits/stdc++.h>
using namespace std;
long long sum[100005];
long long gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int main(){
	freopen("mul.in","r",stdin);
	freopen("mul.out","w",stdout);
	long long n;
	cin>>n;
	for(int i=0;i<n;i++){
		long long a,k;
		cin>>a>>k;
		long long q=pow(10,k);
		sum[i]=q/gcd(max(q,a),min(q,a));
	}
	for(int i=0;i<n;i++) cout<<sum[i]<<endl;
	return 0;
}