deadwing97

EVILAND Editorialist

Aug 11th, 2019
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.22 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int powmod (int a, int b, int p) {
  4.     int res = 1;
  5.     while (b)
  6.         if (b & 1)
  7.             res = int (res * 1ll * a % p),  --b;
  8.         else
  9.             a = int (a * 1ll * a % p),  b >>= 1;
  10.     return res;
  11. }
  12.  
  13. int get_root (int p) {
  14.     vector<int> fact;
  15.     int phi = p-1,  n = phi;
  16.     for (int i=2; i*i<=n; ++i)
  17.         if (n % i == 0) {
  18.             fact.push_back (i);
  19.             while (n % i == 0)
  20.                 n /= i;
  21.         }
  22.     if (n > 1)
  23.         fact.push_back (n);
  24.  
  25.     for (int res=2; res<=p; ++res) {
  26.         bool ok = true;
  27.         for (size_t i=0; i<fact.size() && ok; ++i)
  28.             ok &= powmod (res, phi / fact[i], p) != 1;
  29.         if (ok)  return res;
  30.     }
  31.     return -1;
  32. }
  33.  
  34. const int MX = (1<<18);
  35.  
  36. int T;
  37.  
  38. int n , MOD , goal;
  39.  
  40. int revPow[MX];
  41.  
  42. int arr[MX];
  43.  
  44. int cnt[MX];
  45.  
  46. int main(){
  47.     int T;
  48.     scanf("%d",&T);
  49.     while(T--){
  50.  
  51.         scanf("%d %d %d",&n,&MOD,&goal);
  52.  
  53.  
  54.         int root = get_root(MOD);
  55.  
  56.         memset(revPow , -1 , sizeof(revPow));
  57.         memset(cnt , 0   , sizeof(cnt));
  58.  
  59.         long long cur = 1; revPow[cur] = 0;
  60.  
  61.         int Z = 0;
  62.  
  63.         for(int j = 1 ; ; j++){
  64.             cur *= root; cur %= MOD;
  65.             if(revPow[cur] != -1) break;
  66.             revPow[cur] = j;
  67.         }
  68.  
  69.  
  70.  
  71.         for(int j = 1 ; j <= n ; j++){
  72.             scanf("%d",&arr[j]);
  73.             if(arr[j] == 0){
  74.                 ++Z;
  75.                 arr[j] = 1;
  76.             }
  77.             arr[j] = revPow[arr[j]];
  78.             arr[j] %= (MOD - 1);
  79.             ++cnt[arr[j]];
  80.  
  81.         }
  82.  
  83.         if(goal == 0){
  84.             cout<<Z<<endl;
  85.             continue;
  86.         }
  87.  
  88.         int ans = 0;
  89.  
  90.         goal = revPow[goal] % (MOD - 1);
  91.  
  92.  
  93.         vector < int > divisors;
  94.  
  95.         for(int j = 1 ; j < MOD ; j++)
  96.             if((MOD - 1)%j == 0)
  97.                 divisors.push_back(j);
  98.  
  99.         for(auto D : divisors){
  100.            // cout<<D<<' '<<goal<<' '<<root<<endl;
  101.             if(goal % D == 0) continue;
  102.             int x = cnt[0];
  103.             for(int i = D ; i < MX ; i += D)
  104.                 x += cnt[i];
  105.             ans = max(ans , x);
  106.         }
  107.  
  108.         cout<<n - ans<<endl;
  109.     }
  110.  
  111. }
Add Comment
Please, Sign In to add comment