Acwing 3827. 最小正整数 数学思维gcm或推导

Acwing 3827. 最小正整数

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需要满足:

Acwing 3827. 最小正整数   数学思维gcm或推导

\[1.x \% n == 0\newline 2.x \% 10^k == 0 \]

x要最小,x = gcm(n, 10 ^ k)

解法2:

答案x满足:

Acwing 3827. 最小正整数   数学思维gcm或推导

\[x = c*n \newline (10^k) \% (c*n) == 0\newline =>c * n = 10^k * t = 2^k * 5 ^ k * t\newline =>n = 2^a * 5^b * t,c = 2^x * 5^y \newline =>x = max(0,k - a),y = max(0, k - b) \]

#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;
}
上一篇:C# 收银机打印


下一篇:jQuery 菜单栏 展开与收缩例子