結果
問題 | No.752 mod数列 |
ユーザー |
![]() |
提出日時 | 2020-04-23 18:06:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 983 bytes |
コンパイル時間 | 987 ms |
コンパイル使用メモリ | 60,508 KB |
最終ジャッジ日時 | 2025-01-09 22:50:56 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:9:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 9 | scanf("%jd %d", &p, &q); | ~~~~~^~~~~~~~~~~~~~~~~~ main.cpp:41:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 41 | scanf("%jd %jd", &l, &r); | ~~~~~^~~~~~~~~~~~~~~~~~~
ソースコード
#include <cstdint> #include <cstdio> #include <algorithm> #include <vector> int main() { intmax_t p; int q; scanf("%jd %d", &p, &q); std::vector<intmax_t> d{0}; for (intmax_t i = 1; i*i <= p; ++i) { d.push_back(i); if (i*i < p) d.push_back(p/i); } std::sort(d.begin(), d.end()); std::vector<intmax_t> s{0}; for (size_t i = 1; i < d.size(); ++i) { intmax_t dl = d[i-1]+1; intmax_t dr = d[i]; intmax_t sum = ((p % dl) + (p % dr)) * (dr-dl+1) / 2; s.push_back(sum); } s.insert(s.begin(), 0); for (size_t i = 1; i < s.size(); ++i) s[i] += s[i-1]; auto f = [&](intmax_t r) -> intmax_t { if (r == 0) return 0; auto it = std::upper_bound(d.begin(), d.end(), r); size_t j = it - d.begin(); intmax_t dl = it[-1]+1; intmax_t dr = r; return s[j] + ((p % dl) + (p % dr)) * (dr-dl+1) / 2; }; for (int i = 0; i < q; ++i) { intmax_t l, r; scanf("%jd %jd", &l, &r); printf("%jd\n", f(r)-f(l-1)); } }