QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#724310#9167. Coprime Arraycyl001WA 0ms3908kbC++141.6kb2024-11-08 11:54:402024-11-08 11:54:41

Judging History

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

  • [2024-11-08 11:54:41]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3908kb
  • [2024-11-08 11:54:40]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 1000000000;
int s,x,t;
vector <int> p,r[3],ans;
bool check()
{
	for(int i : p) if(s % i == 0) return false;
	return true;
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)
	{
		x = 1,y = 0;
		return ;
	}
	exgcd(b,a % b,y,x);
	y -= a / b * x; 
}
void crt(int n)
{
	int mi = 1;
	for(int i : p) mi *= i;
	for(int k = 0,v;k < n;k++)
	{
		v = 0;
		for(int i = 0;i < (int)p.size();i++)
		{
			ll x,y;
			exgcd(mi / p[i],p[i],x,y);
			x = (x % p[i] + p[i]) % p[i];
			v = (v + x * (mi / p[i]) % mi * r[k][i] % mi) % mi;
		}
		ans.push_back(v);
	}
}
int main()
{
	scanf("%d%d",&s,&x);
	t = x;
	for(int i = 2;i * i <= t;i++)
		if(t % i == 0)
		{
			p.push_back(i);
			while(t % i == 0) t /= i;
		}
	if(t > 1) p.push_back(t);
	if(check())
	{
		printf("1\n%d\n",s);
		return 0;
	}
	if(p[0] != 2 || s % 2 == 0)
	{
		for(int i : p)
			if(s % i == 1) r[0].push_back(2),r[1].push_back(i - 1);
			else r[0].push_back(1),r[1].push_back((s % i - 1 + i) % i);
		crt(2);
	}
	else
	{
		for(int i : p)
			if(s % i == 2) r[0].push_back(1),r[1].push_back(2),r[2].push_back(i - 1);
			else r[0].push_back(1),r[1].push_back(1),r[2].push_back((s % i - 2 + i) % i);
		crt(3);
	}
	ll sum = 0;
	for(int i : ans) sum += i;
	for(int i = 0;sum > s;i++) while(sum > s && ans[i] - x >= -lim) ans[i] -= x,sum -= x;
	for(int i = 0;sum < s;i++) while(sum < s && ans[i] + x <= lim) ans[i] += x,sum += x;
	printf("%d\n",(int)ans.size());
	for(int i : ans) printf("%d ",i);
	puts("");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

9 6

output:

3
7 1 1 

result:

ok Correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

14 34

output:

2
1 13 

result:

ok Correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

1000000000 223092870

output:

2
818007191 181992809 

result:

ok Correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

2 1000000000

output:

2
1 1 

result:

ok Correct

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3900kb

input:

649557664 933437700

output:

2
933521681 98333 

result:

wrong answer Sum of the elements is not equal to s