QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#448383 | #8782. Schoolgirls | ucup-team173 | Compile Error | / | / | C++14 | 3.4kb | 2024-06-19 15:51:22 | 2024-06-19 15:51:22 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define int ll
using namespace std;
int mod=1e9+7;
int add(int x,int y){
x+=y;
return x>=mod?x-mod:x;
}
int mul(int x,int y){
return (__int128)1*x*y%mod;
}
void adto(int&x,int y){
x+=y;
if(x>=mod)x-=mod;
}
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=mul(ans,a);
a=mul(a,a);
b>>=1;
}
return ans;
}
int isp(int n){
for(int i=2;i*i<=n;i++){
if(n%i==0)return 0;
}
return 1;
}
const int maxn=4e4+10;
int n,m,k;
int p,g;
int points[maxn];
int a[maxn],b[maxn],c[maxn];
int r[maxn];
int id[maxn];
void calc(){
cin>>n>>m>>k;
p=(int(1e10/n))*n+1;
while(p<=1e9||!isp(p))p+=n;
// cout<<p<<"\n";
mod=p;
vector<int>fac;
int tmp=p-1;
for(int i=2;i*i<=tmp;i++){
if(tmp%i==0){
fac.pb(i);
while(tmp%i==0)tmp/=i;
}
}
if(tmp!=1)fac.pb(tmp);
for(g=2;;g++){
int flag=1;
for(int q:fac){
if(qpow(g,(p-1)/q)==1){
flag=0;
break;
}
}
if(flag)break;
}
for(int i=1;i<=n;i++){
points[i]=qpow(g,(i-1)*(p/n));
}
// cout<<"### "<<mod<<" "<<g<<"\n";
for(int i=n+1;i<=n+m;i++){
int a,b,c;
cin>>a>>b>>c;
points[i]=add(add(points[a],points[c]),mod-points[b]);
}
// for(int i=1;i<=n+m;i++){
// cout<<points[i]<<" \n"[i==n+m];
// }
// int superflag=0;
// if(k==6685)superflag=1;
// if(superflag){
// for(int i=1;i<=107;i++){
// int r;
// cin>>r;
// vector<int>rr(r);
// for(int&j:rr)cin>>j;
// if(i==107){
// cout<<r<<" ";
// for(int j:rr)cout<<j<<" ";
// return ;
// }
// }
// }
while(k--){
int r;
cin>>r;
vector<int>id(r);
int sum=0;
int allsame=1;
for(int&i:id){
cin>>i;
adto(sum,points[i]);
if(points[i]!=points[id[0]])allsame=0;
}
if(allsame){
cout<<"Yes\n";
continue;
}
sum=mul(sum,qpow(r,mod-2));
// cout<<"sum "<<sum<<"\n";
if(n*2/__gcd(n,2)%r!=0){
cout<<"No\n";
continue;
}
int ap=points[id[0]];
int et=qpow(g,(p-1)/r);
vector<int>u;
u.pb(ap);
for(int i=1;i<r;i++){
u.pb(add(mul(add(u.back(),mod-sum),et),sum));
}
sort(u.begin(),u.end());
sort(id.begin(),id.end(),[&](int a,int b){
return points[a]<points[b];
});
int flag=1;
for(int i=0;i<r;i++){
if(u[i]!=points[id[i]]){
flag=0;
break;
}
}
if(flag){
cout<<"Yes\n";
}else cout<<"No\n";
}
}
void solve(){
calc();
// cin>>n>>m>>k;
// for(int i=n+1;i<=n+m;i++){
// cin>>a[i]>>b[i]>>c[i];
// }
// for(int i=1;i<=k;i++){
// }
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
/*
*/
Details
answer.code: In function ‘void calc()’: answer.code:2:12: error: expected primary-expression before ‘long’ 2 | #define ll long long | ^~~~ answer.code:7:13: note: in expansion of macro ‘ll’ 7 | #define int ll | ^~ answer.code:48:8: note: in expansion of macro ‘int’ 48 | p=(int(1e10/n))*n+1; | ^~~ answer.code:48:8: error: expected ‘)’ before ‘long’ 48 | p=(int(1e10/n))*n+1; | ~^ | ) answer.code:115:21: error: no matching function for call to ‘__gcd(long long int&, int)’ 115 | if(n*2/__gcd(n,2)%r!=0){ | ~~~~~^~~~~ In file included from /usr/include/c++/13/algorithm:61, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51, from answer.code:1: /usr/include/c++/13/bits/stl_algo.h:1185:5: note: candidate: ‘template<class _EuclideanRingElement> _EuclideanRingElement std::__gcd(_EuclideanRingElement, _EuclideanRingElement)’ 1185 | __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) | ^~~~~ /usr/include/c++/13/bits/stl_algo.h:1185:5: note: template argument deduction/substitution failed: answer.code:115:21: note: deduced conflicting types for parameter ‘_EuclideanRingElement’ (‘long long int’ and ‘int’) 115 | if(n*2/__gcd(n,2)%r!=0){ | ~~~~~^~~~~