洛谷P1447 [NOI2010] 能量采集

TITLE

思路

∑ i = 1 n ∑ j = 1 m 2 gcd ⁡ ( i , j ) − 1 = − n ∗ m + 2 ∑ i = 1 n ∑ j = 1 m gcd ⁡ ( i , j ) \sum_{i=1}^n\sum_{j=1}^m2\gcd(i,j)-1=-n*m+2\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j) ∑i=1n​∑j=1m​2gcd(i,j)−1=−n∗m+2∑i=1n​∑j=1m​gcd(i,j)

∵ ∑ k ∣ n ϕ ( k ) = n \because \sum_{k|n}\phi(k)=n ∵∑k∣n​ϕ(k)=n

∴ ∑ i = 1 n ∑ j = 1 m gcd ⁡ ( i , j ) = ∑ i = 1 n ∑ j = 1 m ∑ k ∣ gcd ⁡ ( i , j ) ϕ ( k ) = ∑ i = 1 n ∑ j = 1 m ∑ k ∣ i , k ∣ j ϕ ( k ) = ∑ k = 1 min ⁡ ( n , m ) ( n / i ) ∗ ( m / j ) ∗ ϕ ( k ) \therefore\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)=\sum_{i=1}^n\sum_{j=1}^m\sum_{k|\gcd(i,j)}\phi(k)=\sum_{i=1}^n\sum_{j=1}^m\sum_{k|i,k|j}\phi(k)=\sum_{k=1}^{\min(n,m)}(n/i)*(m/j)*\phi(k) ∴∑i=1n​∑j=1m​gcd(i,j)=∑i=1n​∑j=1m​∑k∣gcd(i,j)​ϕ(k)=∑i=1n​∑j=1m​∑k∣i,k∣j​ϕ(k)=∑k=1min(n,m)​(n/i)∗(m/j)∗ϕ(k)

∴ ∑ i = 1 n ∑ j = 1 m 2 gcd ⁡ ( i , j ) − 1 = − n ∗ m + 2 ∑ k = 1 min ⁡ ( n , m ) ( n / i ) ∗ ( m / j ) ∗ ϕ ( k ) \therefore \sum_{i=1}^n\sum_{j=1}^m2\gcd(i,j)-1=-n*m+2\sum_{k=1}^{\min(n,m)}(n/i)*(m/j)*\phi(k) ∴∑i=1n​∑j=1m​2gcd(i,j)−1=−n∗m+2∑k=1min(n,m)​(n/i)∗(m/j)∗ϕ(k)

线 性 求 ϕ 线性求\phi 线性求ϕ
欧 拉 筛 + ϕ 性 质 欧拉筛+\phi性质 欧拉筛+ϕ性质
ϕ 性 质 : \phi性质: ϕ性质:
(x is a prime) ϕ ( x ) = x − 1 \phi(x)=x-1 ϕ(x)=x−1
( gcd ⁡ ( x , y ) = 1 ) ϕ ( x ∗ y ) = ϕ ( x ) ∗ ϕ ( y ) (\gcd(x,y)=1)\phi(x*y)=\phi(x)*\phi(y) (gcd(x,y)=1)ϕ(x∗y)=ϕ(x)∗ϕ(y)
(y is a prime, y ∣ x ) , ϕ ( x ∗ y ) = ϕ ( x ) ∗ y y|x),\phi(x*y)=\phi(x)*y y∣x),ϕ(x∗y)=ϕ(x)∗y

CODE

#include<iostream> 
#include<cstdio>
#include<cstring>
using namespace std;
class phiclass
{
	private:
		int *phiarray,*primearray,philen,primelen;
		bool *lightarray;
	public:
		void init(int *phitmp,int *primetmp,bool *lighttmp,int x);
		int phi(int x);
		int prime(int x);
		bool isprime(int x);
};
void phiclass::init(int *phitmp,int *primetmp,bool *lighttmp,int x)
{
	int i,j;
	phiarray=phitmp,primearray=primetmp,lightarray=lighttmp,philen=x,primelen=0;
	memset(phiarray,0,sizeof(phiarray));
	memset(primearray,0,sizeof(primearray));
	memset(lightarray,0,sizeof(lightarray));
	phiarray[1]=1,lightarray[0]=lightarray[1]=1;
	for(i=2;i<=philen;i++)
	{
		if(!lightarray[i])primearray[++primelen]=i,phiarray[i]=i-1;
		for(j=1;j<=primelen&&primearray[j]*i<=philen;j++)
		{
			lightarray[primearray[j]*i]=1;
			if(i%primearray[j])phiarray[primearray[j]*i]=phiarray[i]*(primearray[j]-1);
			else{phiarray[primearray[j]*i]=phiarray[i]*primearray[j];break;}
		}
	}
	return;
}
int phiclass::phi(int x)
{
	return phiarray[x];
}
int phiclass::prime(int x)
{
	return primearray[x];
}
bool phiclass::isprime(int x)
{
	return !lightarray[x];
}
int a[500010],b[500010];
bool c[500010];
int main()
{
	long long n,m,mn,i,ans=0;
	phiclass p;
	for(scanf("%lld%lld",&n,&m),mn=min(n,m),p.init(a,b,c,mn),i=1;i<=mn;i++)ans+=p.phi(i)*(n/i)*(m/i);
	printf("%lld",(ans<<1)-n*m);
	return 0;
}