結果
問題 | No.3081 Make Palindromic Multiple |
ユーザー |
|
提出日時 | 2025-02-25 10:05:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 1,000 ms |
コード長 | 1,828 bytes |
コンパイル時間 | 2,037 ms |
コンパイル使用メモリ | 200,548 KB |
実行使用メモリ | 7,328 KB |
最終ジャッジ日時 | 2025-03-27 13:23:21 |
合計ジャッジ時間 | 4,153 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 54 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; using P=pair<ll,ll>; ll qpow(ll a,ll n,ll mod){ ll ret=1; while(n){ if(n&1) ret=(ret*a)%mod; a=(a*a)%mod; n>>=1; } return ret; } vector<P> prime_factorize(ll N) { vector<P> res; for(ll a=2;a*a<=N;++a){ if(N%a!=0) continue; ll ex=0; while(N%a==0){ ++ex; N/=a; } res.push_back({a,ex}); } if(N!=1) res.push_back({N,1}); return res; } ll Euler_phi(ll n){ vector<pair<ll,ll>> pf=prime_factorize(n); ll res=n; for(auto p : pf){ res/=p.first; res*=(p.first-1); } return res; } int main(){ ll n; cin >> n; if(n%2!=0&&n%5!=0){ cout << 1 << endl; cout << 9 << ' ' << Euler_phi(n) <<endl; return 0; } vector<P> pf=prime_factorize(n); string s; for(auto& [p,e]:pf){ if(p==2||p==5){ ll x=1; for(int i=0;i<e;i++) x*=p; s=to_string(x); reverse(s.begin(),s.end()); while(s.size()<e){ s.push_back('0'); } string t=s; reverse(t.begin(),t.end()); s+=t; break; } } ll k=1; for(auto& [p,e]:pf){ if(p==2||p==5) continue; ll tmp=qpow(10,s.size(),p); if(tmp==1){ for(int i=0;i<e;i++) k*=p; }else{ for(int i=0;i<e-1;i++) k*=p; k*=p-1; } } cout << 1 << endl; cout << s << ' ' << k << endl; } /* Nが2,5を素因数に持たない →10^phi(n)-1、レピュニット数など? N=2^kや5^kがなんとかなるが(rev(str(2^k))00000...0str(2^k))、N=m2^kみたいなケースはどうするん? - 2,5以外の素因数しか持たないmについてmod mで10^kを考察する - rev(s)+sをいい感じに並べる? (rev(s)+s)*(10^len(s)のpoly)で作ろう */