C++(g++ 7.5.0) 解法, 执行用时: 2391ms, 内存消耗: 3336K, 提交时间: 2022-09-16 22:25:29

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define int long long

using namespace std ;

const int N = 1e6 + 5 ;

int mod ; 
void read(int & x) { scanf("%lld" , &x) ; }
void print(int x , char c = '\n') { printf("%lld%c" , x , c) ; }

int qmi(int a , int b = mod - 2) {
    int res = 1;
    while (b) {
        if (b & 1) res = (long long)res * a % mod;
        a = (long long)a * a % mod , b >>= 1;
    }
    return res;
}

int n , m , d ; 
vector<int> q ;
int ans[N] , idx ;

vector<int> get(int n) {
    vector<int> ans; 
    int t = n ; 
    for (int i = 2 ; i * i <= t ; ++ i)
    {
        if (t % i == 0)
        {
            ans.push_back(i) ;
            while (t % i == 0) t /= i ;
        }
    }
    if (t > 1) ans.push_back(t) ;
    return ans ; 
}

void solve()
{
    cin >> n >> d ;
    mod = n ; 
    idx = 0 , q = get(n) ; 
    int Euler = n ;
    for (int p : q) Euler = Euler / p * (p - 1) ;
    q = get(Euler) ;
    
    int G = -1 ; 
    for (int i = 1 ; i < n ; ++ i)
    {
        if (__gcd(i , n) != 1) continue;
        bool fg = 1 ; 
        for (int p : q) {
            if (qmi(i , Euler / p) == 1) 
            {
                fg = 0 ;
                break;
            }
        }
        if (fg) {
            G = i ; 
            break;
        }
    }

    if (~G)
    for (int p = G , i = 1 ; i <= Euler ; p = p * G % mod , ++ i) 
        if (__gcd(Euler , i) == 1)
            ans[++idx] = p ;
    sort(ans + 1 , ans + idx + 1) ;
    cout << idx << '\n' ; 
    for (int i = d ; i <= idx || (puts("") , 0) ; i += d) 
        printf("%d " , ans[i]) ;
}
signed main()
{
    int t ; cin >> t ; 
    while (t--) solve() ; 
    return 0 ; 
}

C++ 解法, 执行用时: 1690ms, 内存消耗: 3992K, 提交时间: 2022-07-14 11:18:31

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL ksm(LL a, LL b, LL mod) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return ans;
}
vector<int> get_gen(int x) {
	int m = x;
	int phi = x;
	for (int i = 2; i * i <= m; i ++ ) {
		if(m % i == 0) {
			phi = (LL)phi * (i-1) / i;
			while(m % i == 0) m /= i;
		}
	}
	if(m != 1) phi = (LL)phi * (m - 1) / m;
	vector<int> pfac;
	m = phi;
	for (int i = 2; i * i <= m; i ++ ) {
		if(m % i == 0) {
			pfac.push_back(i);
			while(m % i == 0) m /= i;
		}
	}
	if(m != 1) pfac.push_back(m);
	vector<int> res;
	for (int k = 1; k < x; k ++ ) {
		int f = 1;
		if(__gcd(k, x) != 1) continue;
		for (int i = 0; i < pfac.size(); i ++ ) {
			int xx = pfac[i];
			if(ksm(k, phi / xx, x) == 1) {
				f = 0;
				break;
			}
		}
		if(f) {
			res.push_back(k);
			break;
		}
	}
	int len = res.size();
	if(len) {
		int k = res[0];
		res.pop_back();
		for (int i = 1; i <= phi; i ++ ) if(__gcd(i, phi) == 1) res.push_back(ksm(k, i, x));
	}
	return res;
} 
int main() {
	int T;
	scanf("%d", &T);
	while(T -- ) {
		int x, d;
		scanf("%d%d", &x, &d);
		auto res = get_gen(x);
		sort(res.begin(), res.end());
		int len = res.size();
		printf("%d\n", len);
		for (int i = d; i <= len; i += d) {
			printf("%d ", res[i-1]);
		}
		puts("");
	}
}