QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#471640#8782. Schoolgirlsucup-team1338Compile Error//C++142.7kb2024-07-11 00:04:432024-07-11 00:04:43

Judging History

你现在查看的是最新测评结果

  • [2024-07-11 00:04:43]
  • 评测
  • [2024-07-11 00:04:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using uint = unsigned int; using i64 = long long; using ui64 = unsigned long long; using i128 = __int128;
mt19937_64 rng(19260817);
ll rand(ll L,ll R){return rng()%(R-L+1)+L;}
ll qpow(ll a,ll b,ll p)
{
	ll ans=1;a=a%p;
	while(b)
	{
		if(b&1) ans=ans*a%p;
		a=a*a%p;b=b/2;
	}
	return ans;
}
vector<int> getp(int n)
{
	vector<int> pn;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0) 
		{
			pn.push_back(i);
			while(n%i==0) n/=i;
		}
	}
	if(n>1) pn.push_back(n);
	return pn;
}
bool isp(ll n) {  // 判断素数
	int a = 0; i64 k = n - 1; while( k % 2 == 0 ) a ++, k /= 2;
	constexpr int tests = 100;
	for( int _ = 1; _ <= tests; _ ++ ) {
		i64 x = rand( 1, n - 1 );
		if( gcd( n, x ) > 1 ) return false;
		i64 y = qpow( x, k, n );
		for( int i = 0; i <= a - 1; i ++ ) {
			if( ( y != 1 && y != n - 1 ) && ( i128 ) y * y % n == 1 ) return false;
			y = ( i128 ) y * y % n;
		}
		if( y != 1 ) return false;
	}
	return true;
}
ll findp(int n)// 返回p p%n=1; 
{
	ll M=1e15;ll k=M/n;
	while(1){ll p=rand(1,k)*n+1;if(isp(p))return p;}
}
ll findg(ll p)// 返回质数p的一个原根 
{
	vector<int> pn=getp(p-1);
	while(1)
	{
		for(ll g=1;g<=p;g++)
		{
			//ll g=rand(1,p-1);
			bool flag=0;
			for(auto x:pn) if(qpow(g,(p-1)/x,p)==1){flag=1;break;}
			if(!flag) return g; 
		} 
		
	}
}
ll findg(ll p,int n)//返回g^((p-1)/n)modp  h^1.h^2....h^n 两两不同 
{
	assert((p-1)%n==0);
	vector<int> pn=getp(n);
	while(1)
	{
		ll g=rand(1,p-1);ll h=qpow(g,(p-1)/n,p);
		bool flag=0;
		for(auto x:pn) if(qpow(h,n/x,p)==1){flag=1;break;}
		if(!flag) return h; 
	}
	
}
void solve( ) {
	int n, m, k; cin>>n>>m>>k;
	int N = 2*n; i64 p = findp( N );
	vector< i64 > z( n + m ); i64 e=findg(p,N);
	for( int i = 0; i < n; i ++ ) z[i] = qpow( e, i*N/n, p );
	for( int i = n; i < n + m; i ++ ) { int a, b, c; cin >> a >> b >> c; a --, b --, c --; z[i] = ( z[a] + z[c] - z[b] + p ) % p; }

	while( k -- ) {
		int r; cin >> r; vector< i64 > I( r ); for( int j = 0; j < r; j ++ ) cin >> I[j], I[j] --;
		i64 z0 = 0; for( int i : I ) z0 = ( z0 + z[i] ) % p;
		vector< i64 > y; for( int i : I ) y.emplace_back( ( ( i128 ) r * z[i] % p - z0 + p ) % p ); sort( y.begin( ), y.end( ) );
		if( N % r != 0 ) {
			if( y[0] == y[r - 1] ) cout << "Yes" << "\n";
			else cout << "No" << "\n";
		}
		else {
			i64 f = qpow(e,N/r,p);
			bool good = true; for( i64 x : y ) { i64 fx = ( i128 ) x * f % p; good &= binary_search( y.begin( ), y.end( ), fx ); }
			if( good ) cout << "Yes" << "\n";
			else cout << "No" << "\n";
		}
	}
}

int main( ) {
	ios::sync_with_stdio( 0 ), cin.tie( 0 ), cout.tie( 0 );
	int T = 1; while( T -- ) solve( ); return 0;
}

詳細信息

answer.code: In function ‘bool isp(ll)’:
answer.code:36:21: error: ‘gcd’ was not declared in this scope
   36 |                 if( gcd( n, x ) > 1 ) return false;
      |                     ^~~