Project Euler 643 2-Friendly

Posted on | 阅读数 次
Words count in article: 594 | Reading time ≈ 3

开启传送门

题目描述

Two positive integers $a$ and $b$ are 2-friendly when $gcd(a,b)=2^t,t>0$. For example, $24$ and $40$ are 2-friendly because $gcd(24,40)=8=2^3$ while $24$ and $36$ are not because $gcd(24,36)=12=2^2\cdot 3$ not a power of $2$.

Let $f(n)$ be the number of pairs, $(p,q)$, of positive integers with $1\leq p<q\leq n$ such that $p$ and $q$ are 2-friendly. You are given $f(10^2)=1031$ and $f(10^6)=321418433$ modulo $1000000007$ .

Find $f(10^{11})$ modulo $1000000007$.

题意

问你所有满足$1\leq p<q\leq 1e11$,并且$gcd(p,q)==2^t$的对数

分析

显然可以对于每个$2^t$单独考虑,不妨设$2^t = x$,可以得到

$$
ans = \sum_{i=1}^{upper/x} \varphi(i)
$$

然后显然是各种筛法搞一下,我这里用的杜教筛,然后稍微推一推就可以得到

$$
s(m) = \frac{m\ast (m+1)}{2} - \sum_{d=2}^{m} s(\lfloor \frac{m}{d} \rfloor)
$$

然后分块一下,递归搞下去就行了$\dots$

代码

给大佬递上我奇丑无比的代码　(/ω＼)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
const long long upper = 1e11;
const int maxm = 2e7+10;
const int mod = 1e9+7;
int add(int a,int b){return (a+b)%mod;}
int mul(long long a,long long b){return (a%mod)*(b%mod)%mod;}
int inv(long long a){ return a==1?1:mul(mod-mod/a,inv(mod%a)); }
int inv2 = inv(2);
bool p[maxm];
int pri[maxm];//质数
int phi[maxm];//欧拉函数前缀和
void init(){
	phi[1] = 1;
	for(int i =2;i<maxm;i++){
		if(!p[i]){
			pri[++pri[0]] = i;
			phi[i] = i-1;
		}
		for(int j = 1;j<=pri[0]&&i*pri[j]<maxm;j++){
			p[i*pri[j]] = true;
			if(i%pri[j]) phi[i*pri[j]] = phi[i]*(pri[j]-1);
			else{
				phi[i*pri[j]] = phi[i]*pri[j];
				break;
			}
		}
	}
	for(int i = 2;i<maxm;i++) phi[i] = add(phi[i],phi[i-1]);//因为只会用到前缀和,所以我们直接预处理成前缀和
}
map<long long,int> mp;
int solve(long long m){
	if(m<maxm) return phi[m];//查表
	if(mp[m]) return mp[m];//记忆化
	int ret = mul(m,mul(m+1,inv2));
	for(long long l = 2,r;l<=m;l = r+1) {//分块
		r = m/(m/l);
		ret = add(ret,mod-mul(solve(m/l),r-l+1));
	}	
	return mp[m] = ret;
}
int main(){
	init();
	int ans = 0;
	for(long long x = 2;x<=upper;x<<=1) {//单独统计每一个2的幂
		cout<<x<<endl;
		ans = add(ans,solve(upper/x));
		ans = add(ans,mod-1);
	}	
	cout<<ans<<endl;
	return 0;
}