QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#693733#9426. Relearn through ReviewNana7#WA 288ms3704kbC++141.3kb2024-10-31 16:39:382024-10-31 16:39:41

Judging History

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

  • [2024-10-31 16:39:41]
  • 评测
  • 测评结果:WA
  • 用时:288ms
  • 内存:3704kb
  • [2024-10-31 16:39:38]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#define I inline
#define int long long
using namespace std;

const int N = 300010;
int a[N];
int n,k;
vector<int> g;
map<int,int> mp;

int gcd(int x,int y) {
	if(!y) return x;
	return gcd(y,x%y);
}
I bool check(int x) {
	int cnt=0;
	for(int i=1;i<=n;++i) if(a[i]%x!=0) cnt++;
	if(!cnt) return 1;
	if(k%x==0) return 0;
	for(int i=1;i<=n;++i) {
		if(a[i]%x!=0&&(a[i]+k)%x!=0) return 0;
	}
	bool apr=0; 
	for(int i=1;i<=n;++i) {
		if(a[i]%x!=0) {
			if(apr&&(a[i-1]%x==0)) {
				return 0;
			}
			else apr=1;
		}
	}
	return 1;
}
I void solve() {
	cin>>n>>k; g.clear(); mp.clear();
	for(int i=1;i<=n;++i) cin>>a[i];
	int ng=-1;
	for(int i=1;i<=n;++i) {
		if(ng==-1) ng=a[i];
		else ng=gcd(a[i],ng);
		if(mp[ng]==0) mp[ng]=1,g.push_back(ng);
	}
	ng=-1;
	for(int i=n;i>=1;--i) {
		if(ng==-1) ng=a[i];
		else ng=gcd(a[i],ng);
		if(mp[ng]==0) mp[ng]=1,g.push_back(ng);
	}
	int ans=1;
	for(auto &t:g) {
		if(check(t)) ans=max(ans,t);
	}
	for(int i=1;i<=n;++i) a[i]+=k;
	ng=a[1];
	for(int i=2;i<=n;++i) ng=gcd(ng,a[i]);
	ans=max(ans,ng);
	cout<<ans<<endl;
}
signed main()
{
	int T; cin>>T;
	while(T--) {
		solve();
	}
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3692kb

input:

2
6 2
5 3 13 8 10 555
3 0
3 6 9

output:

5
3

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 288ms
memory: 3704kb

input:

100000
1 608611451460421713
33155506392034032
1 743116173559300609
6138108577573005
7 364454564010802125
657035115675878115 657035115675878115 657035115675878115 657035115675878115 657035115675878115 292580551665075990 657035115675878115
4 316648374341335221
365788422120542814 182894211060271407 731...

output:

641766957852455745
749254282136873614
657035115675878115
182894211060271407
880411769063535667
560553564512176618
1
962990836390050009
616597869896951268
878097339332572161
188820994675344528
997057718507559252
949074379610491450
2
632093288650732211
1
356502546608886970
789177332497135009
566104642...

result:

wrong answer 7th lines differ - expected: '183698346865682381', found: '1'