Problem Description
Marry likes to count the number of ways to choose two non-negative integers a and b less than m to make a×ba × bmodm≠0m ≠ 0 .
Let’s denote f(m)f ( m )as the number of ways to choose two non-negative integers a and b less than m to makea×ba × bmodm≠0m ≠ 0 .
She has calculated a lot of f(m) for different m, and now she is interested in another functiong(n)=∑m|nf(m)g ( n ) = ∑ m | n f ( m ) . For example,g(6)=f(1)+f(2)+f(3)+f(6)=0+1+4+21=26g ( 6 ) = f ( 1 ) + f ( 2 ) + f ( 3 ) + f ( 6 ) = 0 + 1 + 4 + 21 = 26 . She needs you to double check the answer.
文章图片
Give younn . Your task is to findg(ng ( n ) modulo2642 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≤200001 ≤ T ≤ 20000
1≤n≤1091 ≤ n ≤ 10 9
Output
For each test case, print one integer s, representing g(n) modulo 264.
Sample Input
2
6
514
Sample Output
26
328194
Source
2015ACM/ICPC亚洲区长春站-重现赛（感谢东北师大）
先推一下 ff :
f(m)=m2?∑i=1m∑j=1mm|i?j=m2?∑i=1m∑j=1mm(m,i)|i(m,i)?jf ( m ) = m 2 ? ∑ i = 1 m ∑ j = 1 m m | i ? j = m 2 ? ∑ i = 1 m ∑ j = 1 m m ( m , i ) | i ( m , i ) ? j
可以发现 m(m,i)和i(m,i)m ( m , i ) 和 i ( m , i )已经是互质了，所以要整除m， jj必须是 m(m,i)m ( m , i )的倍数，其数量显然是 (m,i)( m , i )个，则： f(m)=m2?∑i=1m(m,i)f ( m ) = m 2 ? ∑ i = 1 m ( m , i )
这里是老套路，去枚举gcd：最终就有： f(m)=m2?∑d|md??(md)f ( m ) = m 2 ? ∑ d | m d ? ? ( m d )
来看 gg ,所以：
g(n)=∑m|nm2?∑m|n∑d|md?(md)g ( n ) = ∑ m | n m 2 ? ∑ m | n ∑ d | m d ? ( m d )
把d拿到最外层： g(n)=∑m|nm2?∑d|nd∑d|m,m|n?(md)=g(n)=∑m|nm2?∑d|nd∑k|nd?(k)=g(n)=∑m|nm2?∑d|nng ( n ) = ∑ m | n m 2 ? ∑ d | n d ∑ d | m , m | n ? ( m d ) = g ( n ) = ∑ m | n m 2 ? ∑ d | n d ∑ k | n d ? ( k ) = g ( n ) = ∑ m | n m 2 ? ∑ d | n n
【【HDU 5528】Count a * b（推导）】到这里就是去枚举n的所以因子了，用唯一分解来做，然后搜索枚举因子即可。
代码：
#include
#include
#include
#include
#include
#define ullunsigned long long
#define ll long long
#define ul unsigned int
#define maxn 40000
using namespace std;
bool isP[maxn];
int prime[maxn];
int cnt;
void init()
{
for(int i=2;
i1){fac[k]=x;
e[k++]=1;
}
}
ull ans=0;
void dfs(int cur,ull temp)
{
if(cur==k)
{
ans+=temp*temp;
return;
}
dfs(cur+1,temp);
ull now=temp;
for(int i=1;
i<=e[cur];
i++)
{
now*=fac[cur];
dfs(cur+1,now);
}
}
ull mod=0;
int main()
{
mod=~mod;
init();
int t;
cin>>t;
int n;
while(t--)
{
scanf("%d",&n);
int total=1;
getFac(n);
ans=0;
dfs(0,1);
for(int i=0;
i 推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- 线性同余方程组
- 数论|AtCoder Beginner Contest 156 C.Rally