题目描述： Count a * b
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 203 Accepted Submission(s): 114
【搞一波ICPC！|hdu 5528 Count a * b】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×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 264.
Sample Input
2
6
514
Sample Output
26
328194
题解： 经典的数论的题目.比赛时能做出来真是队友给力.
说一下最终的推导方法吧:(公式编辑太麻烦啦..我公式就不写了…http://async.icpc-camp.org/d/203-changchun-2015-b-count-a-times-b 可以看这个链接写的公式)
首先要写出表达式:两部分,前面是m^2, 后面是一个gcd的求和式.两部分前面套了一个枚举约数.
前面的不用看(可以暴力枚举约数,也可以利用积性函数的性质更快一点算).
后面的显然要换序:先只看里面的换序,因为gcd(i,m)和第一层第二层都有关,并且一般都会枚举gcd是谁.
之后可以再换一次序,当然也可以发现是积性的就去推公式.
也可以发现一个公式,然后化简到最简.
最后一步暴力枚举约数. 暴力枚举约数的时候也有一个比较快的小技巧.根据约数排序去除.
听昂神讲的时候学到积性函数可以o(n)的对1e6以内打表 质因数分解复杂度的求1e9的数.
然后推公式的时候gcd(a,b)==k 可变成 gcd(a/k,b/k)==1,写成gcd(m,n)==1, 可变成莫比乌斯反演.然后提到最前面
重点： 数论推公式+换序+积性
代码：
//没利用积性的性质.
#include
#include
#include using namespace std;
typedef unsigned long long ull;
const int N = 1e5;
ull ans;
int n;
int p[N], tot;
int xp[N], num[N], xpn;
int b[N], bn;
bool flag[N];
int Euler() {
int tmp;
tot = 0;
memset(flag, 0, sizeof(flag));
for(int i = 2;
i < N;
++i) {
if(!flag[i]) {
p[tot++] = i;
}
for(int j = 0;
j < tot && 1ll * i * p[j] < N;
++j) {
tmp = i * p[j];
flag[tmp] = true;
if(i % p[j]) {
;
}
else {
break;
}
}
}
}void yue(int x)
{
int xx = x;
xpn = 0;
ans = 0;
for(int i = 0;
i 
