結果
問題 | No.2989 Fibonacci Prize |
ユーザー |
![]() |
提出日時 | 2024-12-14 10:14:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 751 bytes |
コンパイル時間 | 1,886 ms |
コンパイル使用メモリ | 171,864 KB |
実行使用メモリ | 12,516 KB |
最終ジャッジ日時 | 2024-12-14 10:14:33 |
合計ジャッジ時間 | 4,260 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 77 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int N,M,T=-1,MAX=1e9; cin>>N>>M; if(M==1||M==2){ if(N==1)cout<<2; else cout<<0; return 0; } if(N==1){ int64_t ans=M-1; ans*=(M-2); ans/=2; ans+=3; cout<<ans; return 0; } vector<int> F(3); vector<int64_t>R(N,0),RR(N,0); F[1]=F[2]=1; for(int i=3;i<MAX;i++){ F.push_back((F[i-1]+F[i-2])%N); if(F[i-1]==0&&F[i]==1){ T=i-1; break; } } F.push_back(1); for(int i=1;i<=T;i++){ R[(F[i+2]-1+N)%N]++; } int64_t K=(M-2)/T,r=(M-2)%T; for(int i=1;i<=r;i++){ RR[(F[i+2]-1+N)%N]++; } RR[0]++; int64_t ans=0; for(int i=0;i<N;i++){ R[i]*=K; R[i]+=RR[i]; ans+=R[i]*(R[i]-1)/2; } if(F[(M-1)%T]%N==0)ans++; if(F[M%T]%N==0)ans+=2; cout<<ans<<endl; }