AtCoder ARC #044 : A - 素数判定、B - 最短路問題

なんとか全完したもののミスが多いね。
http://arc044.contest.atcoder.jp/tasks/arc044_a
http://arc044.contest.atcoder.jp/tasks/arc044_b

A - 素数判定

自然数Nは以下の何れかを満たす時、Nをほぼ素数と呼ぶ。

• Nが素数
• Nが合成数で、1の位が2,5で割り切れず、各桁の和が3で割り切れない。

Nが与えられたときそれがほぼ素数か判定せよ。

最後の条件がちょっと複雑だが、要は2,3,5のどれでも割り切れなければほぼ素数と見なせる。

ll N;

int pp(ll N) {
	ll i;
	if(N==1) return 0;
	
	for(i=2;i*i<=N;i++) if(N%i==0) {
		return (N%2!=0) && (N%3!=0) && (N%5!=0);
	}
	return 1;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(pp(N)) cout<<"Prime"<<endl;
	else cout<<"Not Prime"<<endl;
}

B - 最短路問題

N頂点の無向グラフがある。
各頂点から頂点1までの最短距離はA[i]だった。
条件を満たすようなグラフの形状は何個あるか。

前提としてA[1]=0でなければならない。
頂点1からの距離がpの点の数をf(p)とする。

距離がpの点は、距離(p-1)の点と１個以上辺をもたなければならない。
また距離pの点同士は辺をもっても持たなくても良い。

前者の条件より、距離pの点が距離(p-1)の点と１個以上辺をもつのは通り。点がf(p)個あるので全体でf(p)乗。
後者の条件より、f(p)個の点は互いに辺をもっても持たなくても良いので、それらの辺は通り。
上記式をpごとに掛算していけば良い。

int N;
int A[101010];
ll num[101010];
ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int ma=0;
	cin>>N;
	FOR(i,N) cin>>A[i], num[A[i]]++, ma=max(ma,A[i]);
	
	if(A[0]!=0 || num[0]!=1) return _P("0\n");
	
	ll ret=1;
	for(i=1;i<=ma;i++) {
		ll need=(modpow(2,num[i-1])+mo-1)%mo;
		ret=ret*modpow(need,num[i])%mo;
		ret=ret*modpow(2,num[i]*(num[i]-1)/2)%mo;
	}
	cout<<ret<<endl;
}

まとめ

Bみたいにやたら総数が増える問題結構好き。