結果
問題 | No.2989 Fibonacci Prize |
ユーザー |
|
提出日時 | 2024-12-14 17:58:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 1,339 bytes |
コンパイル時間 | 1,945 ms |
コンパイル使用メモリ | 200,736 KB |
最終ジャッジ日時 | 2025-02-26 14:27:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 77 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m, p; cin >> n >> m; if(m <= 90){ vector<ll> a = {1, 1}; while(a.size() < m) a.emplace_back(a.rbegin()[1] + a.back()); int ans = 0; for(int l = 0; l < a.size(); l++){ ll sv = 0; for(int r = l; r < a.size(); r++){ sv += a[r]; if(sv > a.back()) break; ans += (sv % n == 0); } } cout << ans << '\n'; exit(0); } if(n == 1){ ll len = m - 2; cout << len * (len + 1) / 2 + 3 << '\n'; return 0; } vector<int> a = {1, 1}, cnt(n); a.reserve(2 * n); do{ a.emplace_back(a.rbegin()[1] + a.back()); if(a.back() >= n) a.back() -= n; }while(a.rbegin()[1] != 1 || a.back() != 1); a.pop_back(); a.pop_back(); const int r = a.size(), d = (m - 2) / r, rem = (m - 2) - r * d; int sv = 0; cnt[0]++; for(int i = 0; i < r; i++){ sv += a[i]; if(sv >= n) sv -= n; cnt[sv] += d; if(i < rem) cnt[sv]++; } ll ans = (a[(m - 1) % r] == 0) * 2 + (a[(m - 2) % r] == 0); for(auto &&v : cnt) ans += (ll)(v) * (v - 1) / 2; cout << ans << '\n'; }