HDU1215七夕节（约数和定理）

题目链接：七夕节

思路：这题数据规模不大，用下这个定理1A

Code：

#include <math.h>
#include <stdio.h>

const int mod = 1e9+7;

int qpow (int a, int b) {
	int ans = 1;
	while (b) {
		if (b & 1) {
			ans = ans * a % mod;
		}
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

int solve (int n) {
	int sum = 1, k, limit = sqrt(n),tmp = n;
	for (int i = 2; i <= limit; i++) {
		if (n % i == 0) {
			k = 0;
			while (n % i == 0) {
				k++;
				n /= i;
			}
			sum *= (1 - qpow(i, k+1)) / (1 - i) % mod;
		}
	}
	if (n != 1) sum *= (1 + n);
	return sum-tmp;
}

int main() {
	int n,T;
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&n);
		printf("%d\n",solve(n));
	}
	return 0;
}