洛谷P2398 GCD SUM

求 思路:n很大,没有办法暴力去计算.想要比较快速地计算,必须要按照gcd的值进行分类. 我们称 a n s k ans_k ansk​为 g c d ( i , j ) = k 的 数 目 gcd(i,j)=k的数目 gcd(i,j)=k的数目. g c d ( i , j ) = k , g c d ( i / k , j / k ) = 1. gcd(i,j)=k,gcd(i/k,j/k)=1. gcd(i,j)=k,gcd(i/k,j/k)=1. 那么显然 i , j 就 是 k 的 若 干 倍 , 令 i = a ∗ k , j = b ∗ k i,j就是k的若干倍,令i=a*k,j=b*k i,j就是k的若干倍,令i=a∗k,j=b∗k 那么根据条件,显然有 g c d ( i / k , j / k ) = g c d ( a , b ) = 1 ; gcd(i/k,j/k)=gcd(a,b)=1; gcd(i/k,j/k)=gcd(a,b)=1; 我们需要知道这样的 ( a , b ) 的 对 数 , 因 为 g c d ( a , b ) = g c d ( b , a ) (a,b)的对数,因为gcd(a,b)=gcd(b,a) (a,b)的对数,因为gcd(a,b)=gcd(b,a) 我们不妨先设 a > b , 然 后 在 统 计 的 时 候 统 一 乘 以 2 即 可 a>b,然后在统计的时候统一乘以2即可 a>b,然后在统计的时候统一乘以2即可 问题变为求这样的 ( a , b ) 对 , 其 中 a > b 且 g c d ( a , b ) = 1 (a,b)对,其中a>b且gcd(a,b)=1 (a,b)对,其中a>b且gcd(a,b)=1 这是什么,这就是欧拉函数啊，小于n且与n互素的个数. 令小于x且与x互素的数目为 ϕ ( x ) \phi(x) ϕ(x),令 M = ( n / k ) M=(n/k) M=(n/k) a n s k = 2 ∗ ∑ i = 1 M ϕ ( i ) ans_k=2*\sum_{i=1}^M\phi(i) ansk​=2∗i=1∑M​ϕ(i) 请注意,上述式子是假设 a ! = b a!=b a!=b情况下才成立的. 对于所有的 i i i,我们重复计算了 g c d ( i , i ) 两 次 , 扣 去 即 可 gcd(i,i)两次,扣去即可 gcd(i,i)两次,扣去即可. 若不会如何写欧拉函数,参考下面个人笔记. https://blog.csdn.net/qq_36018057/article/details/123790815 Ac代码: 爆long long警告.

/*
*/
#include
using namespace std;
typedef long long ll;
const int maxn = 1e5+2;
const int INF = 1e9+7;
#define int long long
typedef pair pii;
int phi[maxn];int sum[maxn];
void phi_table(int n){
	for(int i=2;i