Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int powmod (int a, int b, int p) {
- int res = 1;
- while (b)
- if (b & 1)
- res = int (res * 1ll * a % p), --b;
- else
- a = int (a * 1ll * a % p), b >>= 1;
- return res;
- }
- int get_root (int p) {
- vector<int> fact;
- int phi = p-1, n = phi;
- for (int i=2; i*i<=n; ++i)
- if (n % i == 0) {
- fact.push_back (i);
- while (n % i == 0)
- n /= i;
- }
- if (n > 1)
- fact.push_back (n);
- for (int res=2; res<=p; ++res) {
- bool ok = true;
- for (size_t i=0; i<fact.size() && ok; ++i)
- ok &= powmod (res, phi / fact[i], p) != 1;
- if (ok) return res;
- }
- return -1;
- }
- const int MX = (1<<18);
- int T;
- int n , MOD , goal;
- int revPow[MX];
- int arr[MX];
- int cnt[MX];
- int main(){
- int T;
- scanf("%d",&T);
- while(T--){
- scanf("%d %d %d",&n,&MOD,&goal);
- int root = get_root(MOD);
- memset(revPow , -1 , sizeof(revPow));
- memset(cnt , 0 , sizeof(cnt));
- long long cur = 1; revPow[cur] = 0;
- int Z = 0;
- for(int j = 1 ; ; j++){
- cur *= root; cur %= MOD;
- if(revPow[cur] != -1) break;
- revPow[cur] = j;
- }
- for(int j = 1 ; j <= n ; j++){
- scanf("%d",&arr[j]);
- if(arr[j] == 0){
- ++Z;
- arr[j] = 1;
- }
- arr[j] = revPow[arr[j]];
- arr[j] %= (MOD - 1);
- ++cnt[arr[j]];
- }
- if(goal == 0){
- cout<<Z<<endl;
- continue;
- }
- int ans = 0;
- goal = revPow[goal] % (MOD - 1);
- vector < int > divisors;
- for(int j = 1 ; j < MOD ; j++)
- if((MOD - 1)%j == 0)
- divisors.push_back(j);
- for(auto D : divisors){
- // cout<<D<<' '<<goal<<' '<<root<<endl;
- if(goal % D == 0) continue;
- int x = cnt[0];
- for(int i = D ; i < MX ; i += D)
- x += cnt[i];
- ans = max(ans , x);
- }
- cout<<n - ans<<endl;
- }
- }
Add Comment
Please, Sign In to add comment