結果

問題 No.443 GCD of Permutation
コンテスト
ユーザー Guowen Rong
提出日時 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);
      |         ~~~~~^~~~~~~~~~~~~

ソースコード

diff # 

#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;
}
0