Search on the blog

2020年2月7日金曜日

c++17 で stg::lcm が追加されててハマった話

 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 に gcdlcm が追加されてました。引数を int で渡すとこちらが実行されていたようです。

とりあえずローカルでコンパイルするときに g++17 を使うようにしたものの、サンプルケースにオーバーフローするものがないと意図せず std::lcm の方が呼び出しされていることに気づけないので、自分のライブラリ関数の名前を変えた方がいい気がしています。