結果
問題 | No.886 Direct |
ユーザー | kotamanegi |
提出日時 | 2019-09-13 23:15:19 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,044 ms / 4,000 ms |
コード長 | 2,667 bytes |
コンパイル時間 | 1,498 ms |
コンパイル使用メモリ | 151,568 KB |
実行使用メモリ | 81,016 KB |
最終ジャッジ日時 | 2024-05-07 19:32:10 |
合計ジャッジ時間 | 18,420 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 61 ms
27,788 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 104 ms
26,880 KB |
testcase_03 | AC | 436 ms
27,136 KB |
testcase_04 | AC | 65 ms
26,752 KB |
testcase_05 | AC | 110 ms
26,752 KB |
testcase_06 | AC | 108 ms
26,880 KB |
testcase_07 | AC | 66 ms
26,880 KB |
testcase_08 | AC | 109 ms
26,880 KB |
testcase_09 | AC | 111 ms
26,880 KB |
testcase_10 | AC | 110 ms
26,752 KB |
testcase_11 | AC | 104 ms
26,752 KB |
testcase_12 | AC | 104 ms
26,880 KB |
testcase_13 | AC | 105 ms
26,880 KB |
testcase_14 | AC | 104 ms
26,880 KB |
testcase_15 | AC | 106 ms
26,752 KB |
testcase_16 | AC | 105 ms
26,880 KB |
testcase_17 | AC | 401 ms
27,264 KB |
testcase_18 | AC | 406 ms
27,260 KB |
testcase_19 | AC | 401 ms
27,392 KB |
testcase_20 | AC | 393 ms
27,264 KB |
testcase_21 | AC | 419 ms
27,264 KB |
testcase_22 | AC | 410 ms
27,264 KB |
testcase_23 | AC | 663 ms
52,032 KB |
testcase_24 | AC | 586 ms
50,512 KB |
testcase_25 | AC | 564 ms
43,840 KB |
testcase_26 | AC | 639 ms
49,956 KB |
testcase_27 | AC | 817 ms
68,000 KB |
testcase_28 | AC | 959 ms
75,012 KB |
testcase_29 | AC | 589 ms
81,016 KB |
testcase_30 | AC | 565 ms
61,204 KB |
testcase_31 | AC | 998 ms
80,280 KB |
testcase_32 | AC | 1,032 ms
80,492 KB |
testcase_33 | AC | 1,044 ms
80,416 KB |
testcase_34 | AC | 1,036 ms
80,404 KB |
testcase_35 | AC | 1,044 ms
80,404 KB |
ソースコード
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <algorithm> #include <utility> #include <functional> #include <cstring> #include <queue> #include <stack> #include <math.h> #include <iterator> #include <vector> #include <string> #include <set> #include <math.h> #include <iostream> #include <random> #include<map> #include <iomanip> #include <time.h> #include <stdlib.h> #include <list> #include <typeinfo> #include <list> #include <set> #include <cassert> #include<fstream> #include <unordered_map> #include <cstdlib> #include <complex> #include <cctype> #include <bitset> using namespace std; typedef string::const_iterator State; #define Ma_PI 3.141592653589793 #define eps 1e-5 #define LONG_INF 1e18 #define GOLD 1.61803398874989484820458 #define MAX_MOD 1000000007LL #define GYAKU 500000004LL #define MOD 998244353LL #define seg_size 262144*4 #define REP(a,b) for(long long a = 0;a < b;++a) int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } long long cnter[4000000] = {}; long long wow[4000000] = {}; long long calc(long long start, long long hi) { long long kousuu = (start+hi-1) / hi; long long ende = start - (kousuu-1LL) * hi; long long hoge = ende + start; hoge %= MAX_MOD; hoge *= kousuu; hoge %= MAX_MOD; hoge *= GYAKU; hoge %= MAX_MOD; return hoge; } int main(){ iostream::sync_with_stdio(false); cin.tie(0); long long h, w; cin >> h >> w; long long ans = (h - 1) * w + (w - 1) * h; ans %= MAX_MOD; vector<long long> sosuu; vector<pair<long long, long long>> gogo; for (long long i = 2; i < max(h,w)+1; ++i) { if (wow[i] == 0) { sosuu.push_back(i); for (int q = 1; i * q <= 3000000; ++q) { if (gcd(i, q) == 1) { wow[i * q]++; } else { wow[i * q] += 100000; } } } } for (int i = 2; i < max(h,w)+1; ++i) { if (wow[i] < 100000) { gogo.push_back(make_pair(i, wow[i])); } } for (long long i = 1; i < h; ++i) { cnter[i] = (w - 1LL) * w / 2LL; cnter[i] %= MAX_MOD; } for (int i = 0; i < gogo.size(); ++i) { if (gogo[i].first > h||gogo[i].first > w) break; long long downing = calc(w - gogo[i].first, gogo[i].first); if (gogo[i].second % 2 == 1) { downing = MAX_MOD - downing; } for (int t = 1; gogo[i].first * t < h; ++t) { cnter[gogo[i].first * t] += downing; cnter[gogo[i].first * t] %= MAX_MOD; } } long long tmp = 0; for (long long i = 1; i < h; ++i) { tmp += cnter[i] * 2LL * (h - i); tmp %= MAX_MOD; } ans += tmp; ans %= MAX_MOD; cout << ans<< endl; /* for (int i = 1; i < h; ++i) { for (int q = 1; q < w; ++q) { if (gcd(i, q) == 1) { ans += 2 * (h - i) * (w - q); } } } cout << ans << endl; */ }