48問目

である.
の下10桁を求めよ.

http://projecteuler.net/index.php?section=problems&id=48

実装自体は簡単だと高を括って powMod 関数を作ってみたが, 桁あふれに上手く対処できず, 結局 gmp さんの力を借りることにしました.

#include <stdio.h>
#include <stdlib.h>
#include "powMod.h"
#include <gmp.h>

const long long MODULO = 10000000000LL;

long long solveVer00(int);
char *solveVer01(int);

int main(int argc, char **argv) {
	int number;

	if (argc < 1 + 1) {
		fprintf(stdout, "Error: too few argument.\n");
		return EXIT_FAILURE;
	}

	number = atoi(argv[1]);
//	fprintf(stdout, "Solution: %lld.\n", solveVer00(number));
	fprintf(stdout, "Solution: %s.\n", solveVer01(number));

	return EXIT_SUCCESS;
}

long long solveVer00(int number) {
	int i;
	long long result;

	for (i = 1, result = 0; i <= number; i++) {
		result += powMod(i, i, MODULO);
		result %= MODULO;
	}

	return result;
}

char *solveVer01(int number) {
	mpz_t i;
	mpz_t result;
	mpz_t term;
	mpz_t modulo;
	char *resultString;

	mpz_init(i);
	mpz_init(result);
	mpz_init(term);
	mpz_init(modulo);

	mpz_set_si(result, 0);
	mpz_set_str(modulo, "10000000000", 10);
	for (mpz_set_si(i, 1); mpz_cmp_si(i, number) < 0; mpz_add_ui(i, i, 1)) {
		mpz_powm(term, i, i, modulo);
		mpz_add(result, result, term);
	}

	mpz_clear(i);
	mpz_clear(term);
	mpz_clear(result);
	mpz_clear(modulo);

	mpz_get_str(resultString, 10, result);

	return resultString;
}