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). 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 264
.
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≤109
Output
For each test case, print one integer s
, representing g(n) modulo 2^64
.
Sample Input
2
6
514Sample Output
26
328194
首先，化简f(m),
文章图片
文章图片
（因为0和m对m取模的结果一样,这里把[0,m-1]换为[1,m]。显然，后面那个式子的意思是i和j分别提供m的部分因子。）那么式子就可以化简为:
文章图片
这时，i去掉gcd（m，i）后，已经没用，可以删去，式子变为:
文章图片
（由于
文章图片
）式子化简为：
文章图片
由结论（百度获得）进一步化简为:
文章图片
那么,
文章图片
后面的式子继续化简:（现将d提出来；因为m为n的因子，d为m的因子，设m/d=k，则m=k*d，那么kd|n，即k|（n/d））化简得：
文章图片
由结论得式子为:
文章图片
。那么最后，g（n）就化简为
文章图片
（该）式子的含义为，求出m的所有因子的平方和，再减去n的因子的个数个n。对于求m的所有因子的平方和，可以将n唯一分解，记下每个质因子以及他的指数，然后dfs搜索答案。）#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define ull unsignedlong long
using namespace std;
const int N =1e5+10;
int prime[N],d[50],e[50],cnt,cnt1;
bool vis[N];
ull ans;
void get_prime()
{
for(int i=2;
i<=N-10;
i++)
{
if(!vis[i]) prime[cnt++]=i;
for(int j=0;
j1)
{
d[cnt1]=n;
e[cnt1++]=1;
}
return ;
}
void dfs(int cur,ull div)
{
if(cur==cnt1)
{
//cout<
【HDU - 5528 Count a * b (数论公式推导)】
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
