济南网站建设行知keji,云服务器网站文件夹,wordpress 多租户,贵阳网站建设方案报价Product 1 Modulo N CodeForces - 1514C
题意#xff1a;
在[1,n-1]中选x个数#xff0c;使得乘积mod n 1#xff0c;求x的最大值#xff0c;并输出所选的数
题解#xff1a;
我们设S为所选x个数的乘积 S%n 1说明gcd(S,n)1,即所选的x个数均与n互质#xff0c;如果不…Product 1 Modulo N CodeForces - 1514C
题意
在[1,n-1]中选x个数使得乘积mod n 1求x的最大值并输出所选的数
题解
我们设S为所选x个数的乘积 S%n 1说明gcd(S,n)1,即所选的x个数均与n互质如果不互质不可能%n1 因此只能选与n互质的数 设sum为所有与n互质的数的乘积并对n取模 如果sum1说明这些数都可以选 如果sum1此时sum一定与n互质(因为sum的因子都是与n互质的)那sum这个数也参与了乘积中如果去掉这个数%n就等于1了
代码
#includebits/stdc.h
#define int long long
using namespace std;
const int maxm2e65;
vectorintans;
mapint,intmp;
int n;
void solve(){cinn;int s1;for(int i1;in-1;i){if(__gcd(i,n)!1){mp[i]1;}else{ss*i%n;}}if(s!1)mp[s]1;for(int i1;in-1;i){if(!mp[i]){ans.push_back(i);}}coutans.size()endl;for(int i0;ians.size();i){coutans[i] ;}coutendl;
}
signed main(){ios::sync_with_stdio(0);solve();return 0;
}
