結果
問題 | No.2989 Fibonacci Prize |
ユーザー |
![]() |
提出日時 | 2024-12-14 00:35:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 844 ms / 2,000 ms |
コード長 | 1,016 bytes |
コンパイル時間 | 4,451 ms |
コンパイル使用メモリ | 258,648 KB |
最終ジャッジ日時 | 2025-02-26 13:52:24 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 77 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint1000000007; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 2000000001 #define Inf64 4000000000000000001LL int main(){ long long N,M; cin>>N>>M; if(M<=2){ if(1%N==0){ cout<<2<<endl; } else cout<<0<<endl; return 0; } vector<pair<long long,long long>> t(1,{1%N,1%N}); while(true){ long long x = t.back().second; long long y = x + t.back().first; y %= N; if(x==1%N&&y==1%N)break; t.push_back({x,y}); } map<long long,long long> mp; rep(i,t.size()){ mp[t[i].first] += M / t.size(); } rep(i,M % t.size()){ mp[t[i].first] ++; } mp[t[0].first] --; long long ans = 0; for(auto a:mp){ long long v = a.second; ans += v * (v-1) / 2; } { long long tt = M - 2; if(t[tt%t.size()].first == 0)ans++; } { long long tt = M - 1; if(t[tt%t.size()].first == 0){ ans ++; if(M>=3)ans++; } } cout<<ans<<endl; return 0; }