本文共 1230 字，大约阅读时间需要 4 分钟。

快速幂

求 a 的 b 次方，即  ，最老土的方法是循环。

但是我们知道，当求到  时，直接把  和  相乘就可以得到  。

所以，  =  *  ( *  //可能是奇数)

根据这个式子，可以列出递归代码：

long long mod = ......;//模数template
   
    Tlong long qkpow(long long a,T b) {    if(b == 0) return 1;    if(b == 1) return a;    long long ans = qkpow(a,b / 2);    return ans * ans % mod * qkpow(a,b % 2) % mod;}
   

计数（数论）

题目描述

给定n,m,k都是小于10001的正整数，输出给定的n个数中，其m次幂能被k整除的数的个数。

输出满足条件的数的个数。

输入

两行组成，第一行是n，m，k。

第二行是n个正整数，不超过10001.

输出

输出满足条件的数的个数。

样例输入

3 2 509 10 11

样例输出

1

 题解

这里的能被k整除的数，意思是 模 k 等于零，就把模数定义为 K ，一个一个地算qkpow(an,m) 是否为零就行，就用简明清晰的 qkpow 模板。

#include
   
    #include
    
     #include
     
      #define max(x,y) ((x) > (y) ? (x) : (y))#define min(x,y) ((x) < (y) ? (x) : (y))using namespace std;int read() {    int f = 1,x = 0;char s = getchar();    while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}    while(s >='0' && s <= '9'){x = x * 10 + s - '0';s = getchar();}    return x * f;}int n,m,k,s,ans;int qkpow(int a,int b) {    if(b == 0) return 1;    if(b == 1) return a;    int as = qkpow(a,b >> 1);    return as * as % k * qkpow(a,(b & 1)) % k;}int main() {    n = read();m = read();k = read();    while(n --) {        s = read();        if(qkpow(s,m) % k == 0) ans ++;    }    printf("%d\n",ans);    return 0;}
     
    
   

转载地址：https://blog.csdn.net/weixin_43960414/article/details/89086061 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！