QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#837691 | #3074. Express As The Sum | wtc | TL | 1ms | 3972kb | C++14 | 1.1kb | 2024-12-30 11:50:29 | 2024-12-30 11:50:31 |
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;
const int N=45007;
int n,bz[N],tot,p[N],b[N],c[N],o,pd;
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)
{
printf("%d",n);
fo(i,l,r) printf(" %c %d",i==l?'=':'+',i);
printf("\n");
}
void dfs(int x,int y)
{
if(pd) return;
if(x==o+1)
{
int z=n/y;
if(y==1||!((y&1)^(z&1))) return;
if(z<y) return;
pt(n>>1,(z-y+1)>>1,(z+y-1)>>1);
pd=1;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);
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: 3972kb
input:
3 8 10 24
output:
IMPOSSIBLE 10 = 1 + 2 + 3 + 4 24 = 7 + 8 + 9
result:
ok 3 lines
Test #2:
score: -100
Time Limit Exceeded
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 = 2 + 3 + 4 10 = 1 + 2 + 3 + 4 11 = 5 + 6 12 = 3 + 4 + 5 13 = 6 + 7 14 = 2 + 3 + 4 + 5 15 = 1 + 2 + 3 + 4 + 5 IMPOSSIBLE 17 = 8 + 9 18 = 5 + 6 + 7 19 = 9 + 10 20 = 2 + 3 + 4 + 5 + 6 21 = 6 + 7 + 8 22 = 4 + 5 + ...