結果
問題 |
No.644 G L C C D M
|
ユーザー |
![]() |
提出日時 | 2025-09-22 11:17:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 806 bytes |
コンパイル時間 | 1,436 ms |
コンパイル使用メモリ | 163,464 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-09-22 11:17:48 |
合計ジャッジ時間 | 2,480 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:13:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 13 | scanf("%d%d",&n,&m); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; const int N=1e5+5; const int mod=1e9+7; int n,m; ll jc[N]; bool isp[N]; int mu[N]; vector<int> pr; ll ans; int main(){ scanf("%d%d",&n,&m); if(m>n){ printf("0\n"); return 0; } jc[0]=1; for(int i=1;i<=n;++i)jc[i]=jc[i-1]*i%mod; ll bs=jc[n-2]; n/=m; mu[1]=1; for(int i=2;i<=n;++i){ if(!isp[i]){ pr.push_back(i); mu[i]=-1; } for(int p:pr){ if(p*i>n)break; isp[i*p]=1; if(i%p==0)break; mu[i*p]=-mu[i]; } } for(int i=1;i<=n;++i){ ll cn=n/i; cn=cn*(cn-1)%mod; ans=(ans+mu[i]*cn%mod+mod)%mod; } ans=ans*bs%mod; printf("%lld\n",ans); return 0; }