QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#724307 | #9167. Coprime Array | cyl001 | WA | 0ms | 3960kb | C++14 | 1.5kb | 2024-11-08 11:53:18 | 2024-11-08 11:53:18 |
Judging History
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++) if(ans[i] - x >= -lim) ans[i] -= x,sum -= x;
for(int i = 0;sum < s;i++) if(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: 3956kb
input:
9 6
output:
3 7 1 1
result:
ok Correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
14 34
output:
2 1 13
result:
ok Correct
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3896kb
input:
1000000000 223092870
output:
2 371821451 405085679
result:
wrong answer Sum of the elements is not equal to s