| by XianKa | No comments

【数论】牛客19寒假R1D

链接:https://ac.nowcoder.com/acm/contest/317/D
来源:牛客网


数论题

  • 1.1.首先x+y=n在任何时刻都恒成立。所以如果(x,n)=1那么(y,n)=1也必定成立。
  • 1.2.关于gcd(),记作(),支持几种操作:(n-x,n)=(-x,n)=(x,n)也就是说,一边加到另一边,一边取反,gcd的还是不变的。可以由同余的性质证明。
  • 2.1.每次符合条件k的指数就会增加,所以问题就变成了1-n里面和n互质的数,的和。
  • 2.2.欧拉定理,即费马小定理的推广,介绍了欧拉函数phi(x)表示小于x的数里面,与x互质的数,的个数。有1.1得到的结论,如果xn互质,那么n-x也和n互质。两数之和等于n。所以两两配个对。所有数之和 sum(x)=n \times φ(n) \div 2
  • 2.3.关于nphi(n)的奇偶,如果phi(n)是奇数,那么n/2就会和n互质。但由于n/2还是n的一个约数。所以n只能为2。所以phi(n)为奇数当且仅当n=2,此时也可以整除。同时证明了当n不等于2的时候phi(n)一定为偶数。
  • 3.1.最后快速幂处理答案。注意模
#include
using namespace std;
typedef long long ll;
const ll mod=1000000000+7;
ll n,k,a,b;
ll ksm(ll n,ll m)
{
    ll res=1;
    while(m)
    {
        if(m&1) res=res*n %mod;
        n=n*n %mod;
        m>>=1;
    }
    return res %mod;
}
int main()
{
    cin>>n>>k>>a>>b;
    ll euler=n,bn=n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0) euler=euler/i*(i-1);
        for(;n%i==0;n/=i);
    }
    if(n!=1) euler=euler/n*(n-1);
    ll p=euler/2*bn;
    ll num=a%mod +b%mod;
    cout<

 

发表评论