結果

問題 No.1039 Project Euler でやれ
コンテスト
ユーザー koba-e964
提出日時 2020-04-24 22:16:35
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,933 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 25,728 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-15 03:01:08
合計ジャッジ時間 1,059 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void dfs(long long int, long long int, long long int)’:
main.cpp:44:26: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
   44 |                 printf("%d:",prime);
      |                         ~^   ~~~~~
      |                          |   |
      |                          int long long int
      |                         %lld
main.cpp:45:38: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
   45 |                 rep(i,0,cnt)printf("%d ",temp[i]);printf(":");
      |                                     ~^   ~~~~~~~
      |                                      |         |
      |                                      int       long long int
      |                                     %lld
main.cpp:46:26: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
   46 |                 printf("%d\n",prod);
      |                         ~^    ~~~~
      |                          |    |
      |                          int  long long int
      |                         %lld
main.cpp: In function ‘int main()’:
main.cpp:95:20: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int’ [-Wformat=]
   95 |         printf("%lld ",fff(16));
      |                 ~~~^   ~~~~~~~
      |                    |      |
      |                    |      int
      |                    long long int
      |                 %d

ソースコード

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;
		}
		printf("%d:",prime);
		rep(i,0,cnt)printf("%d ",temp[i]);printf(":");
		printf("%d\n",prod);
		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(){
	printf("%lld ",fff(16));
}
0