广西建设职业技术学院青年网站,泰宁县建设局网站,郑州网站建设一汉狮网络,家在深圳网页版宣传一下 算法提高课整理
CSDN个人主页#xff1a;更好的阅读体验 原题链接
题目描述
给定整数 N N N#xff0c;求 1 ≤ x , y ≤ N 1 \le x,y \le N 1≤x,y≤N 且 gcd ( x , y ) \gcd(x,y) gcd(x,y) 为素数的数对 ( x , y ) (x,y) (x,y) 有多少对。
输入格式
输…宣传一下 算法提高课整理
CSDN个人主页更好的阅读体验 原题链接
题目描述
给定整数 N N N求 1 ≤ x , y ≤ N 1 \le x,y \le N 1≤x,y≤N 且 gcd ( x , y ) \gcd(x,y) gcd(x,y) 为素数的数对 ( x , y ) (x,y) (x,y) 有多少对。
输入格式
输入一个整数 N N N。
输出格式
输出一个整数表示满足条件的数对数量。
数据范围 1 ≤ N ≤ 1 0 7 1 \le N \le 10^7 1≤N≤107
输入样例
4输出样例
4思路
首先考虑暴力。
本题答案为 ∑ i 1 n ∑ j 1 n ∑ p ∈ P [ gcd ( i , j ) p ] \sum_{i1}^{n}\sum_{j1}^{n}\sum_{p \in \mathbb{P}}^{}[\gcd(i,j)p] i1∑nj1∑np∈P∑[gcd(i,j)p]
把 gcd ( i , j ) p \gcd(i,j)p gcd(i,j)p 变成 gcd ( i , j ) 1 \gcd(i,j)1 gcd(i,j)1 然后把 p p p 除到前面的 n n n 里。
即 ∑ p ∈ P ∑ i 1 ⌊ n p ⌋ ∑ j 1 ⌊ n p ⌋ [ gcd ( i , j ) 1 ] \sum_{p \in \mathbb{P}}^{}\sum_{i1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j1}^{\lfloor\frac{n}{p}\rfloor}[\gcd(i,j)1] p∈P∑i1∑⌊pn⌋j1∑⌊pn⌋[gcd(i,j)1]
和 5.5.1 可见的点 相同我们可以将以上代数式变换为 2 × ∑ p ∈ P ∑ i 1 ⌊ n p ⌋ φ ( i ) 1 2 \times\sum_{p \in \mathbb{P}}^{}\sum_{i1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i)1 2×p∈P∑i1∑⌊pn⌋φ(i)1
这里不再进行推导读者可以自行点击上方链接进行阅读。
此时进行计算时间复杂度近似为 O ( n 2 ln n ) \large{O(\frac{n^2}{\ln n})} O(lnnn2)将 n 1 0 7 n10^7 n107 代入计算发现超过 1 0 8 10^8 108在 1 s 1s 1s 的时限内会 TLE \text{TLE} TLE。
我们看到 ∑ i 1 n p φ ( n p ) \large\sum_{i1}^{\frac{n}{p}}\varphi(\frac{n}{p}) ∑i1pnφ(pn) 可以考虑预处理欧拉函数前缀和。
假设 s k ∑ i 1 k φ ( i ) \large{s_k\sum_{i1}^{k}\varphi(i)} sk∑i1kφ(i)则原式可化为 2 × ∑ p ∈ P s ⌊ n p ⌋ 1 \large{2 \times\sum_{p \in \mathbb{P}}^{}s_{\lfloor\frac{n}{p}\rfloor}1} 2×p∈P∑s⌊pn⌋1
此时我们枚举 n n n 的所有质因数进行计算就不会超时。
算法时间复杂度
预处理 φ ( i ) \varphi(i) φ(i) O ( n ) O(n) O(n); 预处理 s i s_i si O ( n ) O(n) O(n); 计算结果 O ( n ln n ) \large{O(\frac{n}{\ln n})} O(lnnn)。
因此最高时间复杂度 O ( n ) O(n) O(n)可以过。
注意 数论题目中开 long long 已经是常识所以很有必要写一条 #define int long long 避免犯错。
AC Code C \text{C} C #include iostream
#define int long longusing namespace std;const int N 1e7 10;int n;
int primes[N], cnt;
int euler[N], s[N];
bool st[N];void get_eulers(int n)
{euler[1] 1;for (int i 2; i n; i ){if (!st[i]){primes[cnt ] i;euler[i] i - 1;}for (int j 0; primes[j] n / i; j ){int t primes[j] * i;st[t] true;if (i % primes[j] 0){euler[t] euler[i] * primes[j];break;}euler[t] euler[i] * (primes[j] - 1);}}
}main()
{scanf(%lld, n);get_eulers(n); // 线性筛质数和欧拉函数for (int i 1; i n; i ) // 预处理欧拉函数前缀和s[i] s[i - 1] euler[i];int res 0;for (int i 0; i cnt; i ) // 枚举 n 以内的质数res 2 * s[n / primes[i]] - 1;printf(%lld\n, res);return 0;
}最后如果觉得对您有帮助的话点个赞再走吧
