結果
問題 | No.886 Direct |
ユーザー | 37zigen |
提出日時 | 2019-09-14 16:59:12 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,614 ms / 4,000 ms |
コード長 | 2,292 bytes |
コンパイル時間 | 674 ms |
コンパイル使用メモリ | 72,328 KB |
実行使用メモリ | 76,872 KB |
最終ジャッジ日時 | 2023-09-20 09:58:36 |
合計ジャッジ時間 | 37,404 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 754 ms
76,764 KB |
testcase_01 | AC | 751 ms
76,696 KB |
testcase_02 | AC | 770 ms
76,564 KB |
testcase_03 | AC | 775 ms
76,872 KB |
testcase_04 | AC | 778 ms
76,628 KB |
testcase_05 | AC | 754 ms
76,560 KB |
testcase_06 | AC | 745 ms
76,692 KB |
testcase_07 | AC | 732 ms
76,608 KB |
testcase_08 | AC | 758 ms
76,556 KB |
testcase_09 | AC | 733 ms
76,548 KB |
testcase_10 | AC | 770 ms
76,544 KB |
testcase_11 | AC | 771 ms
76,760 KB |
testcase_12 | AC | 784 ms
76,572 KB |
testcase_13 | AC | 756 ms
76,760 KB |
testcase_14 | AC | 749 ms
76,676 KB |
testcase_15 | AC | 731 ms
76,540 KB |
testcase_16 | AC | 738 ms
76,756 KB |
testcase_17 | AC | 751 ms
76,616 KB |
testcase_18 | AC | 770 ms
76,556 KB |
testcase_19 | AC | 764 ms
76,608 KB |
testcase_20 | AC | 793 ms
76,628 KB |
testcase_21 | AC | 760 ms
76,760 KB |
testcase_22 | AC | 761 ms
76,604 KB |
testcase_23 | AC | 1,015 ms
76,568 KB |
testcase_24 | AC | 1,118 ms
76,620 KB |
testcase_25 | AC | 936 ms
76,544 KB |
testcase_26 | AC | 973 ms
76,632 KB |
testcase_27 | AC | 1,366 ms
76,572 KB |
testcase_28 | AC | 1,384 ms
76,540 KB |
testcase_29 | AC | 754 ms
76,556 KB |
testcase_30 | AC | 1,143 ms
76,608 KB |
testcase_31 | AC | 1,591 ms
76,724 KB |
testcase_32 | AC | 1,569 ms
76,592 KB |
testcase_33 | AC | 1,567 ms
76,536 KB |
testcase_34 | AC | 1,614 ms
76,568 KB |
testcase_35 | AC | 1,600 ms
76,608 KB |
ソースコード
#include <iostream> #include <string> #include <vector> #include <queue> const long long MOD=(long long)1e9 + 7; long long pow(long long a, long long n) { long long ret=1; for (;n>0;n>>=1,a=a*a%MOD) { if (n%2==1) ret=ret*a%MOD; } return ret; } long long inv(long long a) { return pow(a, MOD-2); } // s + s+1 + s+2 + ... + t long long sum1(long long s, long long t) { if (s>t) return 0; return (s+t)*(t-s+1)%MOD*inv(2)%MOD; } long long gcd(long long a, long long b) { if (a>b) return gcd(b, a); if (a==0) return b; return gcd(b%a, a); } const int NMAX=3123456; long long cnt[NMAX]; long long cnt2[NMAX]; long long cnt3[NMAX]; long long solve(long long H, long long W) { for (int i=0;i<NMAX;++i){ cnt[i]=0; cnt2[i]=0; cnt3[i]=0; } for (long long i=2;i<NMAX;++i) { if (cnt[i]>0) continue; for (int j=i;j<NMAX;j+=i) { if (cnt[j]==-1) continue; cnt[j]++; } if (cnt[i]==1) for (long long j=i*i;j<NMAX;j+=i*i) cnt[j]=-1; } for (int i=2;i<NMAX;++i) { long long sum=sum1(1, (W-1)/i); if (cnt[i]==-1) continue; for (int j=i;j<NMAX;j+=i) { cnt2[j]+=(cnt[i]%2==1?1:-1)*((W-1)/i); cnt3[j]+=(cnt[i]%2==1?1:-1)*sum*i%MOD; if (cnt2[j]>=MOD) cnt2[j]-=MOD; if (cnt3[j]>=MOD) cnt3[j]-=MOD; } } for (int i=0;i<NMAX;++i) cnt3[i]%=MOD; long long a=0, b=0, c=0, ans=0; for (long long p=2;p<H;++p) { c+=(H-p)*W%MOD*(std::max(0LL, W-2)-cnt2[p])%MOD; c-=(H-p)*(sum1(2, W-1)-cnt3[p])%MOD; c=(c+MOD)%MOD; } c=2*c%MOD; b=(H-1)*(W-1)%MOD*(H+W-2)%MOD;//p!=0 && q!=0 && (p==1 || q==1) a=(H*(W-1)%MOD+W*(H-1)%MOD)%MOD;//p=0 || q=0 ans=(a+b+c)%MOD; return ans; } long long brute(long long H, long long W) { long long a=0, b=0, c=0; for (int h1=0;h1<H;++h1) { for (int w1=0;w1<W;++w1) { for (int h2=0;h2<H;++h2) { for (int w2=0;w2<W;++w2) { int h=h2-h1; int w=w2-w1; h=abs(h); w=abs(w); if (gcd(h, w)==1) { if (h==0||w==0) ++a; else if (h==1||w==1) ++b; else ++c; } } } } } a/=2; b/=2; c/=2; return a+b+c; } int main() { long long H, W; std::cin >> H >> W; std::cout << solve(H, W) << std::endl; }