結果

問題 No.443 GCD of Permutation
ユーザー vjudge1
提出日時 2025-01-27 20:50:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 861 bytes
コンパイル時間 1,781 ms
コンパイル使用メモリ 161,312 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-27 20:50:41
合計ジャッジ時間 3,020 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
string n;
bool vis[20];
inline bool is_divisible(string x, ll mod)
{
    ll remainder = 0;
    for (auto ch : n)
        remainder = (remainder * 10 + (ch - '0')) % mod;
    return !remainder;
}
int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    for (auto ch : n)
        vis[ch - '0'] = 1;
    ll gcd = 0;
    for (ll i = 0; i <= 9; i++)
        for (ll j = 0; j < i; j++)
            if (vis[i] && vis[j])
                gcd = __gcd(gcd, 9 * (i - j));
    if (!gcd)
    {
        cout << n << endl;
        return 0;
    }
    for (ll i = gcd; i >= 0; i--)
        if (gcd % i == 0 && is_divisible(n, i))
        {
            cout << i << endl;
            break;
        }
    return 0;
}
0