本文最后更新于 719 天前,其中的信息可能已经有所发展或是发生改变。
Original Link
思想:
- 最大公约数和最小公倍数。
- 要求构造出的数末尾包含 k 个 0,且可以被 n 整除的最小整数;
- 则构造出的数必然也可以被 10k 整除,满足同时被 n 和 10k 整除,
- 显然,该数为 n 和 10k 的最小公倍数时即可满足条件。
- 求最小公倍数即为 n×10k÷gcd(n,10k)。
代码:
| #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; |
| } |