結果
問題 | No.1627 三角形の成立 |
ユーザー |
![]() |
提出日時 | 2021-07-23 22:37:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 44 ms / 1,000 ms |
コード長 | 1,733 bytes |
コンパイル時間 | 1,690 ms |
コンパイル使用メモリ | 175,000 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-07-18 18:34:56 |
合計ジャッジ時間 | 2,655 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007; long long c2(long long x){ x %= MOD; return x * (x + MOD - 1) % MOD * 500000004 % MOD; } int main(){ long long n, m; cin >> n >> m; vector<long long> A; for (int i = 0; i < 3; i++){ A.push_back(n * m - i); } for (int i = 0; i < 3; i++){ if (A[i] % 2 == 0){ A[i] /= 2; break; } } for (int i = 0; i < 3; i++){ if (A[i] % 3 == 0){ A[i] /= 3; break; } } long long ans = 1; for (int i = 0; i < 3; i++){ ans *= A[i] % MOD; ans %= MOD; } int s = max(n, m); vector<long long> F(s, 0); for (int i = 2; i < s; i++){ F[i] += (n % i) * (m % i) % MOD * c2((n / i + 1) * (m / i + 1)) % MOD; F[i] += (i - n % i) * (m % i) % MOD * c2((n / i) * (m / i + 1)) % MOD; F[i] += (n % i) * (i - m % i) % MOD * c2((n / i + 1) * (m / i)) % MOD; F[i] += (i - n % i) * (i - m % i) % MOD * c2((n / i) * (m / i)) % MOD; F[i] %= MOD; } vector<bool> prime(s, true); for (int i = 2; i < s; i++){ if (prime[i]){ for (int j = i * 2; j < s; j += i){ prime[j] = false; } } } vector<int> mobius(s, 1); for (int i = 2; i * i < s; i++){ for (int j = i * i; j < s; j += i * i){ mobius[j] = 0; } } for (int i = 2; i < s; i++){ if (prime[i]){ for (int j = i; j < s; j += i){ mobius[j] *= -1; } } } vector<long long> f(s, 0); for (int i = 1; i < s; i++){ for (int j = i; j < s; j += i){ f[i] += F[j] * mobius[j / i]; f[i] += MOD; f[i] %= MOD; } } for (int i = 2; i < s; i++){ ans -= f[i] * (i - 1) % MOD; ans += MOD; ans %= MOD; } cout << ans << endl; }