結果
問題 | No.1039 Project Euler でやれ |
ユーザー |
|
提出日時 | 2020-04-24 22:18:51 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 1,866 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 25,856 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-08 02:58:02 |
合計ジャッジ時間 | 981 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:94:20: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int’ [-Wformat=] 94 | printf("%lld ",fff(m)); | ~~~^ ~~~~~~ | | | | | int | long long int | %d main.cpp:93:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 93 | scanf("%d",&m); | ~~~~~^~~~~~~~~
ソースコード
/// COPIED FROM http://sugarknri.hatenablog.com/entry/2019/05/31/110204 !!!!!!!!#include <stdio.h>#define ll long long#define rep(i,l,r)for(ll i=(l);i<(r);i++)#define min(p,q)((p)<(q)?(p):(q))ll pom(ll a,ll n,ll m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}#define invp(a,p)pom(a,p-2,p)#define MOD 1000000007ll prime;ll sum;//逆数和ll calc(ll n,ll k){//#GL(k,Z/(p^n)Z)の計算//p^((n-1)kk) * (p^k-p^0)(p^k-p^1)...(p^k-p^(k-1))ll pk=pom(prime,k,MOD);ll m=1;ll ans=pom(prime,(n-1)*k*k,MOD);rep(i,0,k){ans=(ans*(pk-m))%MOD;m=(m*prime)%MOD;}return ans;}ll temp[100];void dfs(ll rest,ll pre,ll cnt){//和がeであるような単調非増加正整数列を作る(⇔分割数をつくるときのやつ)if(rest==0){//Π(Z/p^temp[i])Zに分解したので計算するll prod=1;ll prevsum=0;for(ll i=cnt-1;i>=0;i--){ll cnt=1;while(i>0&&temp[i]==temp[i-1]){i--;cnt++;}ll t=calc(temp[i],cnt)*pom(prime,(prevsum+temp[i]*i)*cnt,MOD)%MOD;prod=(prod*t)%MOD;prevsum+=temp[i]*cnt;}sum=(sum+invp(prod,MOD))%MOD;}rep(i,1,min(rest+1,pre+1)){temp[cnt]=i;dfs(rest-i,i,cnt+1);}}ll f(ll p,ll e){//pべき部分についてΣ1/#Atuを求めるprime=p;sum=0;dfs(e,e,0);return sum;}int fff(ll n){ll x=n;ll pcnt=0;ll p[100],e[100];//素因数分解Πp[i]**e[i]for(ll i=2;i*i<=x;i++)if(x%i==0){ll t=0;while(x%i==0){x/=i;t++;}p[pcnt]=i;e[pcnt]=t;pcnt++;}if(x>1){p[pcnt]=x;e[pcnt]=1;pcnt++;}ll ans=1;rep(i,1,n+1)ans=(ans*i)%MOD;//求めるのはΣ1/#Aut、これはp毎に分解してΠ(Σ1/#Aut)と等しいrep(i,0,pcnt){ans=(ans*f(p[i],e[i]))%MOD;// printf("%lld %lld %lld\n",p[i],e[i],f(p[i],e[i]));}return ans;}int main(){int m;scanf("%d",&m);printf("%lld ",fff(m));}