2603 Brave balloonists

気球に乗って旅する１０人の数学者が赤道を越えて喚起乱舞してシャンパンを開けたらコルクが気球を突き破って落ちて死ぬお話。

気球が落下する前に誰かが犠牲になる（海にダイブする）ことで他の９人を助けることができる。

誰が犠牲になるのか？数学者らしく決めましょうという問題。

１０人が整数ai(1 < ai < 10,000; 0 <= i <= 9)を決定し、a=a1*a2*...*a10を計算する。

このaの約数の個数NのLast Digit（１の位）の番号の人が犠牲になる。誰が犠牲になるか求めよ。

ある数aの約数の個数は、aを素因数分解してみれば簡単にわかる。

例えばa=360ならば、

360 = 2 * 2 * 2 * 3 * 3 * 5

より、360は2が3回、3が2回、5が1回かけられてできていることがわかるので、その約数の個数は

(3+1) * (2+1) * (1+1) = 24個である。（+1は各数を１個もかけない場合）

aiをスキャンするたびに素因数分解してみて、約数の個数をカウントすればいいのだけど、

cc[101]で1から100(=sqrt(10000))までの約数しかカウントしてなくてWA連発してしまった。。。

101とか9973とかがaiとして入ってきた場合ちゃんとカウントできてなかった。反省。

配列使った版。(メモリ400K=4*10000)

#include<cstdio>
#include<cmath>

using namespace std;

int cc[10001];

void hoge(int x) {
    int r = (int)sqrt(x);
    for (int i = 2; i <= r; ++i) {
	int c = 0;
	while (x % i == 0) {
	    x /= i;
	    ++c;
	}
	cc[i] += c;
	if (x == 1) break;
    }
    if (x > r) ++cc[x];
}

int main() {
    for (int i = 0; i < 10; ++i) {
	int x;
	scanf("%d", &x);
	hoge(x);
    }
    int N = 1;
    for (int i = 1; i <= 10000; ++i) {
	N *= cc[i] + 1;
    }
    printf("%d\n", N % 10);
}

無駄をなくそうと慣れないmap使った版(580K)

#include<cstdio>
#include<cmath>
#include<map>

using namespace std;

map<int, int> cc;

void hoge(int x) {
    int r = (int)sqrt(x);
    for (int i = 2; i <= r; ++i) {
	int c = 0;
	while (x % i == 0) {
	    x /= i;
	    ++c;
	}
	cc[i] += c;
	if (x == 1) break;
    }
    if (x > r) ++cc[x];
}

int main() {
    for (int i = 0; i < 10; ++i) {
	int x;
	scanf("%d", &x);
	hoge(x);
    }
    int N = 1;
    map<int, int>::iterator it = cc.begin();
    while (it != cc.end()) {
	//if ((*it).second != 0) printf("%d:%d\n", (*it).first, (*it).second);
	N *= (*it).second + 1;
	++it;
    }
    printf("%d\n", N % 10);
}

メモリ使用量増えとぅ。。。