Acwing 3827. 最小正整数 数学思维gcm或推导
给定两个整数 n和 k。
请你计算,末尾至少有连续 k 个 0,并且可以被 n 整除的最小正整数。
例如,当 n=375,k=4时,满足条件的最小正整数为 30000。
第一行包含整数 TT,表示共有 TT 组测试数据。
每组数据占一行,包含两个整数 n,kn,k。
每组数据输出一行结果,表示满足条件的最小正整数。
所有数据满足 1≤T≤10,1≤n≤1e9,0≤k≤8。
6 375 4 10000 1 38101 0 123456789 8 1 0 2 0
30000 10000 38101 12345678900000000 1 2
解法1:
答案x需要满足:
x要最小,x = gcm(n, 10 ^ k)
解法2:
答案x满足:
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL gcd(LL a, LL b){ return b ? gcd(b, a % b) : a; } int main() { int T; cin>>T; while(T--){ LL n, k; scanf("%lld%lld", &n, &k); LL m = pow(10, k); printf("%lld\n", n / gcd(n, m ) * m); } return 0; }
#include<bits/stdc++.h> using namespace std; typedef long long LL; int get_p(int n, int p) { int res = 0; while(n % p == 0)res ++, n /= p; return res; } int main() { int T; cin>>T; while(T--){ int n, k; scanf("%d%d", &n, &k); int m = pow(10, k); int a = get_p(n, 2), b = get_p(n, 5); printf("%lld\n", n * (LL)(1<<max(0, k - a)) * (LL)pow(5,max(0, k - b))); } return 0; }