結果

問題 No.1039 Project Euler でやれ
ユーザー koba-e964
提出日時 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);
      |   ~~~~~^~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

/// 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 1000000007
ll 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/#AutpΠ(Σ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));
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
1