結果
問題 | No.1627 三角形の成立 |
ユーザー |
![]() |
提出日時 | 2021-07-23 22:21:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 896 ms / 1,000 ms |
コード長 | 2,363 bytes |
コンパイル時間 | 4,090 ms |
コンパイル使用メモリ | 189,280 KB |
最終ジャッジ日時 | 2025-01-23 08:06:15 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#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> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; using mint=modint1000000007; mint s[200020], c[200020]; mint v[200020]; int main() { ll n, m; cin>>n>>m; const mint inv6=mint(6).inv(); for(int i=1; i<=200000; i++){ c[i]=mint(i)*mint(i-1)*mint(i-2)*inv6; s[i+1]=s[i]+c[i]; } mint ans=mint(n*m)*mint(n*m-1)*mint(n*m-2)/mint(6); ans-=mint(m)*mint(n)*mint(n-1)*mint(n-2)/mint(6); ans-=mint(n)*mint(m)*mint(m-1)*mint(m-2)/mint(6); for(int d=1; d<=min(n, m); d++){ set<int> stn, stm; for(int i=1; i<=n/d; i++){ stn.insert(n/(d*i)); //stn.insert(n/(d*i)+1); } for(int i=1; i<=m/d; i++){ stm.insert(m/(d*i)); //stm.insert(m/(d*i)+1); } auto calc=[&](int x, int y){ int x1=x, y1=y; if(x1>y1) swap(x1, y1); return s[x1+1]+s[x1]+(y1-x1)*c[x1]; }; auto sum=[&](int x){ return mint((ll)x*(x+1)/2); }; //map<P, mint> f; for(auto x:stn){ for(auto y:stm){ int rx=n/(x*d), lx=n/((x+1)*d); mint rxs=sum(rx), lxs=sum(lx); int ry=m/(y*d), ly=m/((y+1)*d); mint rys=sum(ry), lys=sum(ly); mint v1=((d+d*x)*(rxs-lxs)-n*mint(rx-lx)), v2=((d+d*y)*(rys-lys)-m*mint(ry-ly)); mint v3=n*mint(rx-lx)-d*x*(rxs-lxs), v4=m*mint(ry-ly)-d*y*(rys-lys); v[d]+=calc(x, y)*v1*v2; v[d]+=calc(x+1, y)*v3*v2; v[d]+=calc(x, y+1)*v1*v4; v[d]+=calc(x+1, y+1)*v3*v4; } } } for(int d=min(n, m); d>=1; d--){ for(int i=2*d; i<=min(n, m); i+=d) v[d]-=v[i]; } ans-=v[1]*2; cout<<ans.val()<<endl; return 0; }