【题解】SDOI-2012 Longge的问题

转载注：

转载自PinkRabbit的博客园

原文地址

以下是转载内容：

题目传送门：链接。

能自己推出正确的式子的感觉真的很好！

题意简述：

求 ∑ni=1gcd(i,n) ∑ i = 1 n g c d ( i , n ) 。 n≤232 n ≤ 2 32 。

题解：

我们开始化简式子：

∑ni=1gcd(i,n) ∑ i = 1 n g c d ( i , n )

=∑nj=1(j×∑ni=1[gcd(i,n)=j]) = ∑ j = 1 n ( j × ∑ i = 1 n [ g c d ( i , n ) = j ] )

=∑nj=1(j×∑ni=1[gcd(i/j,n/j)=1](j|i,j|n)) = ∑ j = 1 n ( j × ∑ i = 1 n [ g c d ( i / j , n / j ) = 1 ] ( j | i , j | n ) )

=∑nj=1(j×ϕ(n/j)(j|n)) = ∑ j = 1 n ( j × ϕ ( n / j ) ( j | n ) )

=∑j|n(j×ϕ(n/j)) = ∑ j | n ( j × ϕ ( n / j ) )

到这里就可以直接计算了。

但是还可以进一步化简！（以下的p为质数）

∑j|n(j×ϕ(n/j)) ∑ j | n ( j × ϕ ( n / j ) )

=∑j|n(n/j×ϕ(j)) = ∑ j | n ( n / j × ϕ ( j ) )

=∑j|n(n/j×(j⋅∏p|jp−1p)) = ∑ j | n ( n / j × ( j ⋅ ∏ p | j p − 1 p ) )

=∑j|n(n⋅∏p|jp−1p) = ∑ j | n ( n ⋅ ∏ p | j p − 1 p )

=n×∑j|n∏p|jp−1p = n × ∑ j | n ∏ p | j p − 1 p

接下来我们令 n=pc11pc22pc33⋯pckk n = p 1 c 1 p 2 c 2 p 3 c 3 ⋯ p k c k ，并定义 fi=pi−1pi f i = p i − 1 p i 。

那么n的因子j可以表示为： j=pc11pc22pc33⋯pckk j = p 1 c 1 p 2 c 2 p 3 c 3 ⋯ p k c k ，满足 0≤ci≤bi 0 ≤ c i ≤ b i 。

那么 ∏p|jp−1p=∏ki=1fi[ci>0] ∏ p | j p − 1 p = ∏ i = 1 k f i [ c i > 0 ] 。

我们观察一类 ∏ki=1fi[ci>0] ∏ i = 1 k f i [ c i > 0 ] 相等的j，它们必要满足在 i i 相等的情况下，cici同时大于 0 0 或cici同时等于 0 0 。

那么这一类的jj有多少个呢？如果这类j有质因子 pq1,pq2,pq3,⋯,pqg p q 1 , p q 2 , p q 3 , ⋯ , p q g 。

那么这类 j j 的答案为∏gi=1fqi∏i=1gfqi，而个数为 ∏gi=1bqi ∏ i = 1 g b q i 。

bi b i 就是原来n的质因数分解的指数。

那么对答案的贡献为： ∏gi=1χqi ∏ i = 1 g χ q i 。这里 χi=fi⋅bi χ i = f i ⋅ b i 。

发现每一个质因子的贡献都是独立的，那么最后我们枚举n的每一个质因子取不取，得到最后的答案： n⋅∏ki=1(χi+1) n ⋅ ∏ i = 1 k ( χ i + 1 ) 。

举个例子：如果n只有3个质因子，那么答案为 n⋅(1+χ1+χ2+χ3+χ1χ2+χ1χ3+χ2χ3+χ1χ2χ3) n ⋅ ( 1 + χ 1 + χ 2 + χ 3 + χ 1 χ 2 + χ 1 χ 3 + χ 2 χ 3 + χ 1 χ 2 χ 3 ) 。

显然可以化简为： n⋅(χ1+1)⋅(χ2+1)⋅(χ3+1) n ⋅ ( χ 1 + 1 ) ⋅ ( χ 2 + 1 ) ⋅ ( χ 3 + 1 ) 。

当然可以类比到质因数更多的情况。

总之，答案就是： n⋅∏ki=1bipi−bi+pipi n ⋅ ∏ i = 1 k b i p i − b i + p i p i 。

代码：

#include<cstdio>
long long n;
long long f(){
    long long ans=n; long long i;
    for(i=;i*i<=n;++i) if(n%i==){
        int b=;
        while(n%i==) ++b,n/=i;
        ans/=i;
        ans*=b*i-b+i;
    } if(n>) ans/=n, ans*=n+n-; 
    return ans;
}
int main(){
    scanf("%lld",&n);
    printf("%lld",f());
    return ;
}