結果

問題 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/#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));
}
0