結果
問題 | No.3028 No.9999 |
ユーザー |
|
提出日時 | 2025-02-21 21:29:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 4,000 ms |
コード長 | 810 bytes |
コンパイル時間 | 3,591 ms |
コンパイル使用メモリ | 281,852 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-21 21:29:10 |
合計ジャッジ時間 | 4,330 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<(b);i++) #define all(a) begin(a),end(a) #define sz(a) (int)(a).size() typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; ll pow_mod(ll a,ll n,ll m){ ll res=1; a%=m; while(n){ if(n%2)res=res*a%m; a=a*a%m;n/=2; } res%=m; if(res<0)res+=m; return res; } int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int N;cin>>N; int phi=N; { int n=N,d=2; while(d*d<=n){ if(n%d==0)phi-=phi/d; while(n%d==0)n/=d; d++; } if(n>1)phi-=phi/n; } vector<int>D; rep(i,1,10010)if(phi%i==0)D.emplace_back(i),D.emplace_back(phi/i); sort(all(D)); D.erase(unique(all(D)),D.end()); for(auto d:D){ if(pow_mod(10,d,N)==1%N){ cout<<d<<endl; return 0; } } assert(1); }