题目链接

Raising Modulo Numbers

题目大意

有T组测试,每组测试输入一个模数p,输入有H组数据,每组数据有a,b, 求a^b%p,各组数据的和再模p。

解题思路

快速幂

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5000;
int t,h;
ll mod,a[N],b[N];
ll quick_mi(ll a, ll b, ll p)//a:底数 b:指数 p:模数
{
    int res=1%p;
    while(b)
    {
        if(b&1) res=a*res%p;
        a=a*a%p;
        b>>=1;
    }
    return res%p;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cout.tie(0);
    std::cin>>t;
    while(t--)
    {
        int ans=0;
        std::cin>>mod>>h;  //模数mod,H组数据
        for(int i=1;i<=h;++i) 
        {
            std::cin>>a[i]>>b[i];
            ans=(ans%mod+quick_mi(a[i],b[i],mod))%mod;
        }
        std::cout<<ans<<'\n';
    }
    return 0;
}

题目链接

a^b

题目大意

求 a 的 b 次方对 p 取模的值,其中 0≤a,b,p≤1e9

解题思路

快速幂

AC代码

#include <iostream>
using namespace std;
typedef long long ll;
ll a,b,mod;
ll quick_mi(ll a, ll b, ll mod) //a表示底数,b表示指数
{
    ll res=1%mod;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return res%mod;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    std::cin>>a>>b>>mod;
    std::cout<<quick_mi(a,b,mod)<<'\n';
    return 0;
}

题目链接

64位整数乘法

题目大意

求a乘b对p取模的值,其中1≤a,b,p≤1e18

解题思路

基于快速幂思想的快速乘


axb=a+a+a+a+……a
ax1=a
ax2=2a
ax4=4a
ax8=8a
……
ax(2^k)=2^kxa
时间复杂度(O(logb))

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,p;
void work(ll a, ll b, ll mod)
{
    ll ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%mod;
        a=a*2%mod;
        b>>=1;
    }
    std::cout<<ans%p<<'\n';
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cout.tie(0);
    std::cin>>a>>b>>p;
    work(a,b,p);
    return 0;
}

题目链接

Sumdiv

题目大意

求A的B次方的所有约数之和,取余9901(1<=A,B<=5e7)

解题思路

AC代码>

#include <stdio.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
const int mod=9901;
int quick_mi(int a, int b)
{
    int res=1; a=a%mod;
    while(b)
    {
        if(b&1) res=res%mod*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res%mod;
}
int sum(int p,int k)
{
    if(k==0) return 1;
    if(k&1) return ((1+quick_mi(p,(k+1)>>1))*sum(p,(k-1)>>1))%mod;
    else return ((1+quick_mi(p,k>>1))*sum(p,(k>>1)-1)%mod+quick_mi(p,k))%mod;
}
int main()
{
    int A,B,ans=1;
    scanf("%d %d",&A,&B);
    rep(i,2,A)
    {
        int cnt=0;
        while(A%i==0)
        {
            cnt++;
            A/=i;
        }
        if(cnt) ans=ans*sum(i,cnt*B)%mod;
    }
    if(A==0) puts("0");
    else printf("%d\n",ans);
    return 0;
}

一个爱折腾且喜欢研究算法的大学生