QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#837707 | #3074. Express As The Sum | wtc | WA | 22ms | 5568kb | C++14 | 1.2kb | 2024-12-30 11:59:07 | 2024-12-30 11:59:08 |
Judging History
answer
#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=(l);i<=(r);++i)
#define fd(i,l,r) for(int i=(l);i>=(r);--i)
#define fu(i,l,r) for(int i=(l);i<(r);++i)
#define ll long long
using namespace std;
void out(int x){if(x>9)out(x/10);putchar(48+x%10);}
const int N=45007;
int n,bz[N],tot,p[N],b[N],c[N],o,pd;
vector<int>d;
void init(int n)
{
fo(i,2,n)
{
if(!bz[i])
{
p[++tot]=i;
for(int j=i+i;j<=n;j+=i) bz[j]=1;
}
}
}
void pt(int n,int l,int r)
{
out(n);
fo(i,l,r) putchar(' '),putchar(i==l?'=':'+'),putchar(' '),out(i);
putchar('\n');
}
void dfs(int x,int y)
{
if(pd) return;
if(x==o+1){d.push_back(y);return;}
fu(i,0,c[x]) dfs(x+1,y),y*=b[x];
dfs(x+1,y);
}
void work()
{
scanf("%d",&n);n*=2;
int m=n;o=0;pd=0;
for(int i=1;i<=tot&&p[i]*p[i]<=m;++i)
{
if(m%p[i]==0)
{
m/=p[i];b[++o]=p[i];c[o]=1;
while(m%p[i]==0) m/=p[i],c[o]++;
}
}
if(m>1) b[++o]=m,c[o]=1;
dfs(1,1);
for(int y:d)
{
int z=n/y;
if(y==1||!((y&1)^(z&1))) continue;
if(z<y) continue;
pt(n>>1,(z-y+1)>>1,(z+y-1)>>1);
return;
}
if(!pd) printf("IMPOSSIBLE\n");
}
int main()
{
init(45000);
int T;scanf("%d",&T);
while(T--) work();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4020kb
input:
3 8 10 24
output:
IMPOSSIBLE 10 = 1 + 2 + 3 + 4 24 = 7 + 8 + 9
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 22ms
memory: 5568kb
input:
10866 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...
output:
IMPOSSIBLE IMPOSSIBLE 3 = 1 + 2 IMPOSSIBLE 5 = 2 + 3 6 = 1 + 2 + 3 7 = 3 + 4 IMPOSSIBLE 9 = 4 + 5 10 = 1 + 2 + 3 + 4 11 = 5 + 6 12 = 3 + 4 + 5 13 = 6 + 7 14 = 2 + 3 + 4 + 5 15 = 7 + 8 16 = 4 + 5 + 6 17 = 8 + 9 18 = 3 + 4 + 5 + 6 19 = 9 + 10 20 = 2 + 3 + 4 + 5 + 6 21 = 10 + 11 22 = 4 + 5 + 6 + 7 23 =...
result:
wrong answer 16th lines differ - expected: 'IMPOSSIBLE', found: '16 = 4 + 5 + 6'