Codeforcesの
k-roundingという問題を解いたらWAが出た。
「nとkが与えられるので、末尾に0がk個以上ついてnで割れる最小の自然数を求めよ」という問題で、nと10^k の最小公倍数を求めれば良さそうなので、以下のようなコードをsubmit。
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define ALL(x) (x).begin(), (x).end()
const double PI = acos(-1);
long long gcd(long long a, long long b) {
if (b == 0)
return a;
return gcd(b, a%b);
}
long long lcm(long long a, long long b) {
return a / gcd(a, b) * b;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
int x = 1;
REP (i, k) x *= 10;
cout << lcm(n, x) << endl;
return 0;
}
結果Wong Answer。
詳細なテストケースを見てみると、n = 123456789, k = 8 で 1566078208 と出力されている。試しにローカルで動かしてみると12345678900000000と正答を出力している。
上のコードでは main の中では int を使っているけど引数としてlcmに渡した時点でlong longになるのでオーバーフローはしないはずだが、試しにmainを以下のように変えてsubmitしてみると予想に反してAC。
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
long long n, k;
cin >> n >> k;
long long x = 1;
REP (i, k) x *= 10;
cout << lcm(n, x) << endl;
return 0;
}
サーバでは g++17 で実行されるけどローカルだとg++17じゃないなと気づいて、もしやと思って調べると std に
gcd と
lcm が追加されてました。引数を int で渡すとこちらが実行されていたようです。
とりあえずローカルでコンパイルするときに g++17 を使うようにしたものの、サンプルケースにオーバーフローするものがないと意図せず std::lcm の方が呼び出しされていることに気づけないので、自分のライブラリ関数の名前を変えた方がいい気がしています。
