結果

問題 No.896 友達以上恋人未満
コンテスト
ユーザー RasShalGul
提出日時 2026-08-23 22:02:22
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 665 ms / 3,500 ms
+ 983µs
コード長 1,273 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,804 ms
コンパイル使用メモリ 355,764 KB
実行使用メモリ 136,576 KB
最終ジャッジ日時 2026-08-23 22:03:09
合計ジャッジ時間 6,160 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define int long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
signed main(){
	//freopen("friend.in","r",stdin);
	//freopen("friend.out","w",stdout);
	IOS
	int M,N,mulX,addX,mulY,addY,mod;
	cin>>M>>N>>mulX>>addX>>mulY>>addY>>mod;
	vector<int>X(M),Y(M),A(M),B(M);
	for(int i=0;i<M;i++){
		cin>>X[i];
	}
	for(int i=0;i<M;i++){
		cin>>Y[i];
	}
	for(int i=0;i<M;i++){
		cin>>A[i];
	}
	for(int i=0;i<M;i++){
		cin>>B[i];
	}
	vector<int>cnt(mod,0);
	for(int i=0;i<M;i++){
		cnt[X[i]]+=Y[i];
	}	
	int x=X.back(),y=Y.back();
	for(int i=M;i<N;i++){
		x=(x*mulX+addX)%mod;
		y=(y*mulY+addY)%mod;
		cnt[x]+=y;
	}	
	vector<bool>is_prime(mod,true);
	for(int p=2;p<mod;p++){
		if(is_prime[p]){
			for(int x=(mod-1)/p;x>0;x--){
				cnt[x]+=cnt[x*p];
			}
			for(int i=2*p;i<mod;i+=p){
				is_prime[i]=false;
			}
		}
	}
	int ans=0;
	for(int i=0;i<M;i++){
		int a=A[i],b=B[i],c=0;
		if(a<mod){
			c+=cnt[a];
		}
		if(a*b<mod){
			c-=cnt[a*b];
		}
		cout<<c<<"\n";
		ans^=c;
	}
	int a=A.back(),b=B.back();
	for(int i=M;i<N;i++){
		a=((a*mulX+addX+mod-1)%mod)+1;
		b=((b*mulY+addY+mod-1)%mod)+1;
		int c=0;
		if(a<mod){
			c+=cnt[a];
		}
		if(a*b<mod)
			c-=cnt[a*b];
		ans^=c;
	}
	cout<<ans;
	return 0;
}
0