GCJJぷらくてぃす

EPOCH予選延期でほげ。

前解いたソースをあげます。結局Cは問題文読むのを放棄したまま読んでいないけどA,Bだけ。

A. 数珠繋ぎ

問題分かりにくいけど、分かったら明らかに何か法則性があることが見えてくる。ていうかn=30の時点で慣れてる人は気づく。

そして、それを考えてみると、二進数で1から順番に列挙したものと等価なことが分かる。

例えば、n=3なら、

000→001→010→011→100→101→110→111→000

よって、ループは2^n周期で発生し、周期内で、2^n-1回目に指パッチンした時全部ライトが点いているのでほげ。

#include <iostream>
using namespace std;

int main(){
	int T,n,k;
	cin >> n; T = 1;
	while(cin >> n >> k){
		cout << "Case #" << T++ << ": " << ( (k+1)%(1<<n) == 0 ? "ON" : "OFF" ) << endl;
	}
}

B. 数の集合

制約を見てみると区間篩ですよアピールをしている。

篩かけるだけのループだと重複取り除くのがなんかびみょーに困難だったので、数と素因数の関係でグラフを構築して、O(nm)で独立したグラフの個数を数えるという方法でやった。定数項重すぎてLarge1分くらいかかってアレだったがGCJなので良い。

ソース中では素因数なら負、普通に数なら正みたいな感じで辺をつないでいる。

#include <iostream>
#include <stack>
#include <vector>
#include <cstring>
using namespace std;

int output(int n){
	static int T = 1;
	cout << "Case #" << T++ << ": " << n << endl;
}

#define PRIME_MAX 1000000
vector<bool> prime(PRIME_MAX+1,true);
 
void init_prime(){
	prime[0] = prime[1] = false;
	for(int i=2;i*i<=PRIME_MAX;i++)
		if(prime[i]) for(int j=i*i;j<=PRIME_MAX;j+=i)prime[j] = false;
}

vector<int> graph_[2*(1000001)];
char done_[2*(1000001)];
int main(){
	init_prime();
	vector<int> *graph = &graph_[1000001];
	char *done = &done_[1000001];
	int T; cin >> T;
	long long a,b,p;
	while(cin >> a >> b >> p){
		for(int i = 0 ; i < 2*(1000001) ; i++)
			graph_[i].clear();
		memset(done_,0,sizeof(done_));
		int cnt = 0;
		for(long long i = p ; i <= 1e6 ; i++){
			if( prime[i] ){
				for(long long j = a+(i-a%i)%i ; j <= b ; j+=i){
					graph[j-a].push_back(-i);
					graph[-i].push_back(j-a);
				}
			}
		}
		int ans = 0;
		for(long long i = a ; i <= b ; i++){
			if(!done[i-a]){
				ans++;
				done[i-a] = true;
				stack<int> S;
				S.push(i-a);
				while(S.size()){
					int s = S.top(); S.pop();
					//if(s>=0)cout << s+a << " ";
					for(int i = 0 ; i < graph[s].size() ; i++){
						int t = graph[s][i];
						if(!done[t]){
							S.push(t);
							done[t] = true;
						}
					}
				}
				//cout << endl;
			}
		}
		output(ans);
	}	
}

C

日本語難しかった。