結果
問題 |
No.434 占い
|
ユーザー |
![]() |
提出日時 | 2016-10-23 01:22:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 37 ms / 2,000 ms |
コード長 | 1,697 bytes |
コンパイル時間 | 743 ms |
コンパイル使用メモリ | 94,032 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-23 17:47:34 |
合計ジャッジ時間 | 1,992 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <cassert> #include <iostream> #include <algorithm> #include <stack> #include <queue> #include <vector> #include <set> #include <map> #include <bitset> using namespace std; #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define mp(a,b) make_pair(a,b) #define pb(a) push_back(a) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<<x<<endl #define fi first #define se second #define INF 2147483600 vector<int> primes; // x^n mod long mod_pow(long x, long n, long mod){ long res=1; while(n>0){ if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res; } int main(){ #define SZ 100000 vector<int> divs(SZ+1, 0); //divs[i] := iを割り切る素数のひとつ, 素数なら0 for(int i=2; i<=SZ; i++) if(divs[i]==0){ for(long j=(long)i*i; j<=SZ; j+=i) divs[j]=i; } int tc; scanf("%d\n", &tc); rep(loops, tc){ vector<int> vec; char c; while(scanf("%c", &c)){ if(c=='\n') break; vec.pb(c-'0'); } int n =vec.size(); int res = 0; bool isZero = (vec[0]==0); vector<int> comb(9,0); //combinationの素因数分解 rep(i,n){ if(vec[i]!=0) isZero=false; long cc=1; repl(j,2,9) cc *= mod_pow(j, comb[j], 9); res = (res + vec[i] * cc) % 9; int a = n-1-i; int b = i+1; while(divs[a]>0){ comb[divs[a]%9]++; a /= divs[a]; } comb[a%9]++; while(divs[b]>0){ comb[divs[b]%9]--; b /= divs[b]; } comb[b%9]--; } if(!isZero && res==0) res=9; printf("%d\n", res); } return 0; }