Codeforces 180 B. Divisibility Rules

問題

ある数が2で割り切れるかは、下一桁が2で割れるかを見ればよい。このような判別の仕方を2-typeという。
ある数が3で割り切れるかは各桁の和が3で割れるかを見ればよい。このような判別の仕方を3-typeという。
ある数が6で割り切れるかは、2-typeと3-typeの両方のチェックが必要である。このように、判別の仕方を複数組み合わせる判別の仕方を6-typeという。
ある数が11で割り切れるかは、偶数桁の和と奇数桁の和の差が11で割り切れるかを見ればよい。このような判別の仕方を11-typeという。
ある数が7で割り切れるかは、わからない。わからないものを7-typeという。

このように、b進数で数dで割り切れるかを知るには、どのタイプの判別を使えばよいかを答えよ。
複数の判別の仕方が使える場合、上で先に述べられたものを使うものとする。
2-typeの場合、下何桁を見ればよいかも出力せよ。

制約条件

2≦b, d≦100

方針

一生懸命場合わけして調べる。
3-typeと11-typeは、b % dの値を見れば判別できる。

そうでない場合、各素因数ごとにどのタイプで判別できるかを見る。
複数の判別が必要な場合は6-type.
b ^ n % di == 0なら2-type.
nが必要な桁数。

ソースコード

map<int, int> fac(int n){
	map<int, int> res;
	for(int i = 2; i*i <= n; i++) if(n % i == 0){
		int c = 0;
		while(n % i == 0) n /= i, c++;
		res[i] = c;
	}
	if(n > 1) res[n] = 1;
	return res;
}
void run(){
	int d, b;
	cin >> b >> d;
	map<int, int> f = fac(d), g = fac(b);
	
	if(b % d == 1){
		cout << "3-type" << endl;
		return;
	}
	if(b % d == d-1){
		cout << "11-type" << endl;
		return;
	}
	
	int two = 0;
	bool three = 0, eleven = 0;
	fr(i, f){
		if(!g.count(i->first)){
			int p = 1;
			rep(j, i->second) p *= i->first;
			if(b % p == 1) three = 1;
			else if(b % p == p-1) eleven = 1;
			else{
				cout << "7-type" << endl;
				return;
			}
		}
		else two = max(two, (g[i->first] + i->second - 1) / g[i->first]);
	}
	if((two != 0) + three + eleven > 1) cout << "6-type" << endl;
	else if(two){
		cout << "2-type" << endl;
		cout << two << endl;
	}
	else if(three) cout << "3-type" << endl;
	else if(eleven) cout << "11-type" << endl;
	else assert(0);
}