結果
問題 |
No.443 GCD of Permutation
|
ユーザー |
|
提出日時 | 2025-01-27 18:29:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,355 bytes |
コンパイル時間 | 1,516 ms |
コンパイル使用メモリ | 160,292 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-27 18:29:59 |
合計ジャッジ時間 | 3,112 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 28 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:43:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 43 | scanf("%s", s + 1); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> #define lowbit(x) x & (-x) #define pi pair<ll, ll> #define ls(k) k << 1 #define rs(k) k << 1 | 1 #define fi first #define se second using namespace std; typedef __int128 __; typedef long double lb; typedef double db; typedef unsigned long long ull; typedef long long ll; const int N = 1e5 + 10, M = 10; inline ll read(){ ll x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9'){ if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9'){ x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * f; } inline void write(ll x){ if(x < 0){ putchar('-'); x = -x; } if(x > 9) write(x / 10); putchar(x % 10 + '0'); } int n, ans; char s[N]; int a[N]; bool f[M]; int main(){ scanf("%s", s + 1); n = strlen(s + 1); for(int i = 1; i <= n; ++i){ a[i] = s[i] - '0'; f[a[i]] = 1; } bool F = 1; int t = a[1]; for(int i = 2; i <= n; ++i) F &= (t == a[i]); if(F){ printf("%s\n", s + 1); return 0; } for(int i = 0; i <= 9; ++i) for(int j = 0; j < i; ++j) if(f[i] && f[j]) ans = __gcd(ans, 9 * (i - j)); for(int x = ans; x >= 1; --x){ if(ans % x != 0) continue; int t = 0; for(int i = 1; i <= n; ++i) t = (10 * t + a[i]) % x; if(!t){ write(x); putchar('\n'); break; } } return 0; }