# SGU 117 - Counting

## 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.

## Sample Input

 1 2  4 2 50 9 10 11 12 

## Sample Output

 1  1 

## Solution

### 快速幂

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32  #include using namespace std; typedef unsigned long long ull; ull Pow(ull x, ull y, ull z); int main() { ull nTmp; int N, M, K; while(cin >> N >> M >> K) { int nCnt = 0; for(int i = 1; i <= N; i++) { cin >> nTmp; if(Pow(nTmp, M, K) == 0) { nCnt++; } } cout << nCnt << endl; } return 0; } ull Pow(ull x, ull y, ull z) { if(y == 1) { return x % z; } ull nTmp = Pow(x, y / 2, z); if(y & 1) { return (ull)nTmp * nTmp * x % z; } else { return (ull)nTmp * nTmp % z; } } 

### 质因数分解

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53  #include #include using namespace std; const int MAX = 10240; int X[MAX], Y[MAX]; void Fact(int x, int *p); int main() { int nTmp; int N, M, K; while(cin >> N >> M >> K) { int nCnt = 0; memset(Y, 0, sizeof(Y)); Fact(K, Y); for(int i = 1; i <= N; i++) { memset(X, 0, sizeof(X)); cin >> nTmp; Fact(nTmp, X); for(int i = 0; i < MAX; i++) { X[i] *= M; } bool bFlag = true; for(int j = 0; j < MAX; j++) { if(X[j] < Y[j]) { bFlag = false; break; } } if(bFlag) { nCnt++; } } cout << nCnt << endl; } return 0; } void Fact(int x, int *p) { for(int i = 2; i <= x; i++) { if(x % i == 0) { while(x % i == 0) { (*(p + i))++; x /= i; } } } }