HDU|HDU 5528 Count a * b （2015长春站B题&&积性函数）
设 h[n] 为 a?b=0 的个数。
f[n]=n2?h[n]g[n]=∑m|nf[m]=∑m|n(m2?h[m])=∑m|nm2?∑m|nh[m]
【HDU|HDU 5528 Count a * b （2015长春站B题&&积性函数）】对于 h[n]
h[n]=∑i=1n∑j=1n(gcd(i?j,n)=n)=∑i=1n∑j|ngcd(i,n),1<=j<=n1=∑i=1ngcd(i,n)=∑i=1n∑d|gcd(i,n)?(d)=∑d|n?(d)∑d|i,1<=i<=n1=∑d|n?(d)?nd
显然 h[n] 是积性函数， ∑m|nh[m] 也是积性函数。
对于 n=pα 时。
∑m|nh[m]=∑m|n∑d|m?(d)?nd=∑i=0α(pi+∑j=1i(pj?pj?1)pi?j)=∑i=0αpi+p?1p∑i=0αi?pi=(α+1)pα
最后一步化简：错位相消。
设 n=pα11pα22...pαkk
∑m|nh[m]=(α1+1)?(α2+1)?...?(αk+1)?pα11?pα22?...?pαkk=?(n)?n
所以：
g[n]=∑m|nm2?n??(n)
暴力枚举m的值，总的复杂度是 o(n??√) 。
小 trick ：
题目中要求对 264 取模，实际上就是用 unsigned long long 运算。
代码：
#include
#define uLL unsigned long long
#define LL long long
#define FOR(i,x,y)for(int i = x;
i < y;
++ i)
#define IFOR(i,x,y) for(int i = x;
i > y;
-- i)using namespace std;
const int maxn = 100010;
int prime[maxn];
bool check[maxn];
void Get_Prime(){
memset(check,false,sizeof(check));
prime[0] = 0;
FOR(i,2,maxn){
if(!check[i]){
prime[++prime[0]] = i;
}
FOR(j,1,prime[0]+1){
if(i*prime[j] > maxn)break;
check[i*prime[j]] = true;
if(i%prime[j] == 0) break;
}
}
}vector fac;
int p[30],p_len,cnt[30];
void dfs(int wei,int u){
if(wei >= p_len){fac.push_back(u);
return;
}
dfs(wei+1,u);
int q = p[wei];
FOR(i,0,cnt[wei]){
dfs(wei+1,u*q);
q = q*p[wei];
}
}int n;
void work(){
uLL res = (uLL)n;
p_len = 0;
memset(cnt,0,sizeof(cnt));
FOR(i,1,prime[0]+1){
if(prime[i] > n/prime[i])break;
if(n%prime[i] == 0) p[p_len++] = prime[i];
while(n%prime[i] == 0){cnt[p_len-1] ++;
n /= prime[i];
}
}
if(n > 1){p[p_len++] = n;
cnt[p_len-1] = 1;
}
FOR(i,0,p_len){
res *= ((uLL)cnt[i]+1);
}
fac.clear();
dfs(0,1);
uLL ans = 0;
FOR(i,0,(int)fac.size()){
uLL v = fac[i];
ans += v*v;
}
ans = ans - res;
cout 推荐阅读
- 2019年PB|2019年PB County Senior Open, 保龄生涯（64）
- CountDownLatch-线程并发的发令枪
- SQL优化（二）|SQL优化（二） 快速计算Distinct Count
- 24、CountIF函数和CountIFS函数
- python基础-numpy.bincount详解
- 【JUC】CountDownLatch共享节点队列
- HDU 5528【2015长春现场赛 B】 Count a * b
- hdu5289|hdu5289 Assignment（极差＜k的子区间数量，单调性证明+双指针+单调队列）
- hdu|2016 Multi-University Training Contest 1 C Game(hdu 5725)
- HDU-5628-Clarke-and-math-狄利克雷卷积