117
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
typedef vector<int> vi; 
typedef vector<string> vs;
typedef vector<vi> vvi; 
typedef pair<int,int> ii; 
#define sz(a) int((a).size()) 
#define pb push_back 
#define all(c) (c).begin(),(c).end() 
//#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++) 
#define present(c,x) ((c).find(x) != (c).end()) 
#define cpresent(c,x) (find(all(c),x) != (c).end()) 
#define FOR(_i,_n) for(int (_i) = 0; (_i) < (_n); (_i)++)
 
#define INPUT_FILE "xo.in"
#define OUTPUT_FILE "xo.out"
 
/*  (a^b)%n  */
int ModExp(unsigned int a,unsigned int b,unsigned int n)
{
    int d = 1;
    int k = 31;
 
    while((b&(1<<k)) == 0)k--;
    while(k != -1)
    {
        d = (d*d)%n;
        if(b&(1<<k)) d = (d*a)%n;
        k--;
    }
    return d;
}
 
int main()
{
#ifdef ALEX
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
//    freopen(INPUT_FILE, "r", stdin);
//    freopen(OUTPUT_FILE, "w", stdout);
#endif
 
    int n,m,k;
    int c = 0;
    cin >> n >> m >> k;
 
    for(int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        if(ModExp(t,m,k) == 0)
            c++;
    }
 
    cout << c;
 
    return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.