首页 > 代码库 > SGU - 117 - Counting （快速幂取模！）

SGU - 117 - Counting （快速幂取模！）

2024-08-07 19:35:32   218人阅读

SGU - 117

Counting
Time Limit: 250MS Memory Limit: 4096KB 64bit IO Format: %I64d & %I64u

Submit Status

Description

Find amount of numbers for given sequence of integer numbers such that after raising them to the M-th power they will be divided by K.

Input

Input consists of two lines. There are three integer numbers N, M, K(0<N, M, K<10001) on the first line. There are N positive integer numbers ? given sequence (each number is not more than 10001) ? on the second line.

Output

Write answer for given task.

Sample Input

4 2 50
9 10 11 12

Sample Output

1
Author: Michael R. Mirzayanov
Resource: PhTL #1 Training Contests
Date: Fall 2001

Source




题意：第一行先给出n,m,k三个整数，第二行给出n个整数，判断这些整数的m的次方是否能被k整除，，简单快速幂即可。。


AC代码：


#include <cstdio>
#include <cstring>
#include <algorithm>  
using namespace std;  

int q_pow(int n, int m, int k)  
{  
    int result=1;  
    while(m)  //快速幂 
    {  
        if(m&1)     //判断是否为奇数 
        result=(result*n)%k;   
        n=n*n%k;   
        m>>=1;  
    }  
    return result%k;  
}  

int main()  
{  
    int n, m, k;  
    while(scanf("%d %d %d", &n, &m, &k)!=EOF)  
    {  
        int ans = 0;  
        for(int i=0; i<n; i++)  
        {  
        	int a;
            scanf("%d", &a);  
            if(q_pow(a, m, k)==0)  ans++;  
        }  
        printf("%d\n", ans);  
    }  
    return 0;  
}


SGU - 117 - Counting （快速幂取模！）


联系
我们