結果
問題 | No.1039 Project Euler でやれ |
ユーザー |
👑 ![]() |
提出日時 | 2020-02-18 10:55:44 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 951 bytes |
コンパイル時間 | 955 ms |
コンパイル使用メモリ | 31,744 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-08 02:57:09 |
合計ジャッジ時間 | 1,950 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include<stdio.h>#define M 1000000007int powmod(long long a,int n,int m){long long x=1;a%=m;while(n){if(n%2)x=x*a%m;a=a*a%m;n/=2;}return x;}int ee[100]={100};//番兵int dfs(int p,int rest,int cnt){if(rest==0){long long ans=1;ee[cnt+1]=0;//番兵int idx=0;for(int i=1;i<=cnt;i++){int c=i,d=i;while(ee[c+1]==ee[i])c++;while(ee[d-1]==ee[i])d--;ans=ans*(powmod(p,cnt+1-d,M)-powmod(p,cnt-i,M))%M;idx+=ee[i]*(d-1)+(ee[i]-1)*c;}ans=ans*powmod(p,idx,M)%M;return powmod(ans,M-2,M);}long long ans=0;for(int i=1;i<=ee[cnt]&&i<=rest;i++){ee[cnt+1]=i;ans+=dfs(p,rest-i,cnt+1);}return ans%M;}int f(int n){long long ans=1;for(int i=1;i<=n;i++)ans=ans*i%M;for(int p=2;p*p<=n;p++)if(n%p==0){int e=0;while(n%p==0)n/=p,e++;ans=ans*dfs(p,e,0)%M;}if(n!=1)ans=ans*dfs(n,1,0)%M;return (ans+M)%M;}int main(){int n;scanf("%d",&n);printf("%d\n",f(n));}