2017 Multi-University Training Contest - 第二场 07 If the starlight never fade （数论）

落日映苍穹つ 2022-06-11 02:20 68阅读 0赞

题目链接：  
[HDU 6051][]

题意：  
f(i)  表示满足(x\+y) i ≡x i %p  中 (x,y)  的对数，其中，1≤x≤p−1,1≤y≤m.   
给你一个非负数 m  和素数 p ，让你求∑ p−1 i=1 if(i) ，答案mod1e9\+7 。

题解：  
数学题。

令 g  为 p  的原根，x=g a ,y=g b  。  
那么有(g a \+g b ) i =g ai %p 。即(1\+g b−a ) i =1%p 。  
令1\+g b−a =g k  ，则有g ki =1%p ，即ki%(p−1)=0 。

因为 0<k<p−1 ，所以 k  的取值有gcd(i,p−1)−1 个，递推回去，可知x=y∗inv(g k −1) ,故x 的取值也是gcd(i,p−1)−1 个。

所以我们最后只需要求m∑ p−1 i=1 \{ i∗gcd(i,p−1)−i\} 。  
其中∑ p−1 i=1 i ，我们可以直接求出。

而另一部分∑ p−1 i=1 i∗gcd(i,p−1) ，我们可以通过枚举gcd 的值，化为∑ d|(p−1) d 2 ∑ p−1d  k=1 k∗\[gcd(k,p−1d )=1\] 。  
然后根据公式∑ n i=1 i∗\[gcd(i,n)=1\]=(nφ(n)\+\[n=1\])/2 求解。  
其中，φ(n) 为欧拉函数。

AC代码：

#include<bits/stdc++.h>
    const int mod = 1e9+7;
    using namespace std;
    typedef long long ll;
    
    int mod_mul(int a,int b)
    {
        ll c = 1LL * a * b;
        return c - c / mod * mod;
    }
    
    int euler(int n) 
    {
        int ret = n;
        int i;
        for(i = 2 ; i * i <= n ; i ++)
        {
            if(n % i == 0)
            {
                ret = ret - ret / i;
                while(n % i == 0)
                {
                    n /= i;
                }
            }
        }
        if(n > 1)
        {
            ret = ret - ret / n;
        }
        return ret;
    }
    
    int solve(int n)
    {
        int ans = 0;
        int tmp = 0;
        for(int i = 1 , j ; i * i <= n; i++)
        {
            j = n / i;
            if(i * j == n)
            {
                tmp = mod_mul( (1LL * j * euler(j) + ( j == 1 ) ) / 2 % mod, mod_mul( i , i ) );
                if((ans += tmp) >= mod) ans -= mod;
    
    
                if(i != j)
                {
                    tmp = mod_mul( (1LL * i * euler(i) + ( i == 1 ) ) / 2 % mod, mod_mul( j , j ) );
                    if((ans += tmp) >= mod) ans -= mod;
                }
    
            }
        }
        ans -= mod_mul( mod_mul( n, n + 1), 500000004);
        if(ans < 0) ans += mod;
        return ans;
    }
    int main()
    {
        int t;
        int m,p,cas=0;
        scanf("%d",&t);
        while(t--)
        {
            cas++;
            scanf("%d%d",&m,&p);
            int ans = mod_mul( solve(p - 1), m );
            printf("Case #%d: ",cas);
            printf("%d\n",ans);
        }
        return 0;
    }

[HDU 6051]: http://acm.hdu.edu.cn/showproblem.php?pid=6051