結果
問題 | No.886 Direct |
ユーザー | kotamanegi |
提出日時 | 2019-09-13 23:15:19 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,109 ms / 4,000 ms |
コード長 | 2,667 bytes |
コンパイル時間 | 1,398 ms |
コンパイル使用メモリ | 114,336 KB |
実行使用メモリ | 84,592 KB |
最終ジャッジ日時 | 2023-08-20 12:57:06 |
合計ジャッジ時間 | 19,097 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 65 ms
27,432 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 109 ms
27,364 KB |
testcase_03 | AC | 464 ms
28,324 KB |
testcase_04 | AC | 66 ms
27,832 KB |
testcase_05 | AC | 109 ms
27,032 KB |
testcase_06 | AC | 110 ms
27,460 KB |
testcase_07 | AC | 66 ms
27,508 KB |
testcase_08 | AC | 110 ms
28,448 KB |
testcase_09 | AC | 109 ms
27,684 KB |
testcase_10 | AC | 108 ms
27,676 KB |
testcase_11 | AC | 109 ms
27,112 KB |
testcase_12 | AC | 108 ms
27,256 KB |
testcase_13 | AC | 108 ms
27,004 KB |
testcase_14 | AC | 109 ms
27,992 KB |
testcase_15 | AC | 107 ms
28,348 KB |
testcase_16 | AC | 109 ms
27,604 KB |
testcase_17 | AC | 471 ms
28,016 KB |
testcase_18 | AC | 480 ms
27,672 KB |
testcase_19 | AC | 462 ms
28,304 KB |
testcase_20 | AC | 441 ms
28,488 KB |
testcase_21 | AC | 484 ms
27,800 KB |
testcase_22 | AC | 478 ms
28,184 KB |
testcase_23 | AC | 692 ms
55,084 KB |
testcase_24 | AC | 657 ms
51,000 KB |
testcase_25 | AC | 593 ms
45,400 KB |
testcase_26 | AC | 666 ms
52,988 KB |
testcase_27 | AC | 753 ms
70,140 KB |
testcase_28 | AC | 979 ms
78,076 KB |
testcase_29 | AC | 637 ms
84,592 KB |
testcase_30 | AC | 611 ms
62,304 KB |
testcase_31 | AC | 1,083 ms
83,172 KB |
testcase_32 | AC | 1,050 ms
83,596 KB |
testcase_33 | AC | 1,063 ms
83,884 KB |
testcase_34 | AC | 1,109 ms
81,724 KB |
testcase_35 | AC | 1,097 ms
82,428 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; */ }