結果
問題 | No.886 Direct |
ユーザー |
![]() |
提出日時 | 2019-09-13 22:03:42 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 403 ms / 4,000 ms |
コード長 | 1,521 bytes |
コンパイル時間 | 1,521 ms |
コンパイル使用メモリ | 103,424 KB |
実行使用メモリ | 19,740 KB |
最終ジャッジ日時 | 2024-07-04 09:42:57 |
合計ジャッジ時間 | 14,490 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; const ll MOD=1e9+7; const int MAX=3000030; vector<ll> prime; bool isprime[MAX]; void sieve(){ for(ll i=3; i<MAX; i+=2){ isprime[i]=1; } isprime[2]=1; prime.push_back(2); for(ll i=3; i<MAX; i++){ if(isprime[i]){ prime.push_back(i); for(ll j=2*i; j<MAX; j+=i){ isprime[j]=0; } } } return; } int m[3000030]; void mobius(int n){ fill(m+1, m+n, 1); for(auto p:prime){ for(int i=p; i<n; i+=p){ int x=i; x/=p; if(x%p==0) m[i]=0; else m[i]*=(-1); } } } ll h, w; ll calc(ll x){ ll a=(h-1)/x, b=(w-1)/x; if(a==0 || b==0) return 0; ll ret=h*w%MOD*a%MOD*b%MOD; ret+=MOD-x*w%MOD*b%MOD*(a*(a+1)/2%MOD)%MOD; ret+=MOD-x*h%MOD*a%MOD*(b*(b+1)/2%MOD)%MOD; ret%=MOD; ret+=x*x%MOD*(a*(a+1)/2%MOD)%MOD*(b*(b+1)/2%MOD)%MOD; ret%=MOD; return ret; } int main() { cin>>h>>w; ll ans=(h-1)*w+(w-1)*h; ans%=MOD; sieve(); mobius(3000010); ll s=0; for(int i=1; i<=max(h, w)+1; i++){ if(m[i]==0) continue; ll c=calc(i); (s+=(MOD+m[i])*c)%=MOD; } ans=(ans+2*s)%MOD; cout<<ans<<endl; return 0; }