pid=3970">链接

题解:www.cygmasot.com/index.php/2015/08/17/hdu_3970

给定n

。。。并不会怎样递推。

。

思路:

然后这是公式：

q=2%2C2%2C4%2C4%2C8%2C12%2C20%2C32%2C60&language=english&go=Search">点击打开链接

a(n) = 1/n * sum_{d divides n and d is odd} 2^(n/d) * phi(d).

d最大是n，也就是1e9,要计算1e9的phi，所以容斥来算phi.

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <sstream>

#include <stdlib.h>

#include <string.h>

#include <limits.h>

#include <vector>

#include <string>

#include <time.h>

#include <math.h>

#include <iomanip>

#include <queue>

#include <stack>

#include <set>

#include <map>

const int inf = 1e9;

const double eps = 1e-8;

const double pi = acos(-1.0);

template <class T>

inline bool rd(T &ret) {

	char c; int sgn;

	if (c = getchar(), c == EOF) return 0;

	while (c != '-' && (c<'0' || c>'9')) c = getchar();

	sgn = (c == '-') ?

-1 : 1;

	ret = (c == '-') ?

0 : (c - '0');

	while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');

	ret *= sgn;

	return 1;

}

template <class T>

inline void pt(T x) {

	if (x < 0) { putchar('-'); x = -x; }

	if (x > 9) pt(x / 10);

	putchar(x % 10 + '0');

}

using namespace std;

const int N = 1e5 + 10;

const int mod = 1e9 + 7;

typedef long long ll;

typedef pair<int, int> pii;

int Pow(int x, int y){//高速幂

	int ans = 1;

	while (y){

		if (y & 1)ans = (ll)ans*x%mod;

		y >>= 1;

		x = (ll)x*x%mod;

	}

	return ans;

}

int prime[N], primenum;//素数表

void PRIME(int Max_Prime){

	primenum = 0;

	prime[primenum++] = 2;

	for (int i = 3; i <= Max_Prime; i += 2)

	for (int j = 0; j<primenum; j++)

	if (i%prime[j] == 0)break;

	else if (prime[j]>sqrt((double)i) || j == primenum - 1)

	{

		prime[primenum++] = i;

		break;

	}

}

void add(int &x, int y){ x += y; if (x >= mod)x -= mod; }//加法

void go(int x, vector<int>&Pri, vector<int>&Num){//分解质因数

	Pri.clear(); Num.clear();

	while (!(x & 1))x >>= 1;

	for (int i = 1; (ll)prime[i] * prime[i] <= x; i++){

		if (x%prime[i])continue;

		Pri.push_back(prime[i]);

		Num.push_back(0);

		while (x%prime[i] == 0)x /= prime[i], Num[Num.size() - 1]++;

	}

	if (x != 1 && (x&1))Pri.push_back(x), Num.push_back(1);

}

vector<int>_pri, _num;

void cal(int id, int mul, int siz, int sor, int &now){//容斥算欧拉函数

	if (id == _pri.size()){

		if (mul == 1)return;

		if (siz & 1)now += sor / mul;

		else now -= sor / mul;

		return;

	}

	cal(id + 1, mul, siz, sor, now);

	cal(id + 1, mul*_pri[id], siz + 1, sor, now);

}

int phi(int x){

	if (x == 1)return 1;

	go(x, _pri, _num);

	int now = 0;

	cal(0, 1, 0, x, now);

	return x - now;

}

int ans, n;

vector<int>pri, num;

void dfs(int id, int d){

	if (id == pri.size())

	{

		add(ans, (ll)Pow(2, n / d) * phi(d) % mod);

		return;

	}

	for (int i = 0; i <= num[id]; i++){

		dfs(id + 1, d);

		d *= pri[id];

	}

}

int main(){

	PRIME(1e5);

	int T; rd(T);

	while (T--){

		rd(n);

		go(n, pri, num);

		ans = 0;

		dfs(0, 1);

		pt((ll)ans*Pow(n, mod - 2) % mod); puts("");

	}

	return 0;

}