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

2023-12-21 14:23:39

Acwing 3827. 最小正整数

给定两个整数 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需要满足：

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

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

解法2：

答案x满足：

\[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;
}

码农公寓