最小正整数

Original Link

思想：

• 最大公约数和最小公倍数。
  • 要求构造出的数末尾包含 \(k\) 个 \(0\)，且可以被 \(n\) 整除的最小整数；
  • 则构造出的数必然也可以被 \(10^k\) 整除，满足同时被 \(n\) 和 \(10^k\) 整除；
  • 显然，该数为 \(n\) 和 \(10^k\) 的最小公倍数时即可满足条件。
  • 求最小公倍数即为 \(n \times 10^k \div \gcd(n, 10^k)\)。

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL gcd(LL n, LL m){
    if(n % m == 0) return m;
    return gcd(m, n % m);
}

LL f(LL k){
    LL sum = 1;
    while(k --) sum *= 10;
    return sum;
}

void solve(){
    int n, k; cin >> n >> k;
    cout << n * f(k) / gcd(n, f(k)) << endl;
}

int main(){
    int _; cin >> _;
    while(_ --) solve();
    return 0;
}