经典小知识融合数论题（hdu-5528）

B - Count a * b

Marry likes to count the number of ways to choose two non-negative integers a and b less than m to make a×b mod m≠0.

Let's denote f(m) as the number of ways to choose two non-negative integers a and b less than m to make a×b mod m≠0.

She has calculated a lot of f(m) for different m, and now she is interested in another function g(n)=∑m|nf(m)g(n)=∑m|nf(m). For example, g(6)=f(1)+f(2)+f(3)+f(6)=0+1+4+21=26. She needs you to double check the answer.

Give you n. Your task is to find g(n) modulo 2^64.

Input

The first line contains an integer T indicating the total number of test cases. Each test case is a line with a positive integer n.

1≤T≤20000
1≤n≤10^9

Output

For each test case, print one integer ss, representing g(n)g(n) modulo 264264.

Sample Input

2
6
514

Sample Output

26
328194

这道题就是让你求在 a和b在（0到n-1）范围内有多少a*b%n不等以0，求出不等于0的个数。

由题意显然可以得0到n-1内一共有n^2个a*b的组合。观察图中的给出的示例：table4：

我们可以观察到第几行和6的的gcd是多少，本行中出现的0的次数就为几。这个可以通过gcd（每次跳几步）*n（一共跳n步）/（在n的范围内）。又因为gcd肯定为n的因子。所以出现的0的次数可以得到。为本行的值和n的gcd。我们又看出第0行所有的值是0，同时0和n无法求gcd。但是我们可以将第0行看作第n行，这样使所有的行满足情况。

公式如下：

经典小知识融合数论题（hdu-5528）

最后我们可以通过g（n）求解。

要想做出这道题，首先你要先知道几个推论：

phi（x）为x的欧拉值。

1〉i从1到n：gcd（i，n）求和 = phi（n/d）*d （d为n的因子）求和

我们可以知道n的gcd肯定是n的因子，1到n与n的gcd为1的数量为phi（n），1到n与n的gcd的为2的数量等于与（n/2）的gcd值为1的所以为phi（n/2）......则可以得到上式。

2〉交换求和次序

3〉x的因子的欧拉和等于x

可以通过欧拉函数的性质得到（用质因子分解求欧拉函数值的过程）。求n的欧拉就是用n减去和n的gcd为n的因子（不包括1）的数的个数，因为1到n内所有数和n的gcd都是n的因子。这样和n的gcd为n的因子的数全加一边就是1到n的所有数了。

4〉将累加转换累乘（本质用质因子分解优化）

nn 为n的质因子个数，pi为质因子的值，ki的pi的指数

我们都知道n的因子和为 [pi^(ki+1)-1]/(pi-1), i从1到nn的累乘。

则n的因子的平方和也可得。

n的因子个数为 i从1到nn ，（ki+1）的累乘。

代码如下：

#include<bits/stdc++.h>
const int maxn = 1e5+5;
typedef long long ll;
using namespace std;
int prime[maxn],cnt;
bool isprime[maxn];
void init()
{
    cnt=0;
	for(ll i=2;i<maxn;i++)
	{
		if(!isprime[i])
		{
		   prime[cnt++] = i;
		   for(ll j=i*i;j<maxn;j+=i)
		   isprime[j] =	true;
		}
	}
} 
int main()
{
	init();
	int t,num;
	ll n,tn,tm;
	scanf("%d",&t);
	while(t--)
	{
		tn=1;
		tm=1;
		scanf("%lld",&n);
		ll nn = n;
		for(int i=0;i<cnt&&prime[i]*prime[i]<=nn;i++)
		{
			if(nn%prime[i])
			continue;
		    num=0;
		    ll tt = prime[i];
			while(nn%prime[i]==0) {
			nn/=prime[i];
			tt*=prime[i];
			num++;
		   }
		   ll a=(tt-1)/(prime[i]-1),b=tt+1,c=prime[i]+1;
		   tn*=(num+1);
		   if(a%c==0) tm*=a/c*b;
		   else tm*=b/c*a;
		}
		if(nn>1)
		{
		tn*=2;
		tm*=(nn*nn+1);
	    }
		printf("%lld\n",tm-tn*n);
	}
	return 0;
}

经典小知识融合数论题（hdu-5528）

B - Count a * b

相关推荐