QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#724310 | #9167. Coprime Array | cyl001 | WA | 0ms | 3908kb | C++14 | 1.6kb | 2024-11-08 11:54:40 | 2024-11-08 11:54:41 |
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++) 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;
}
详细
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