Different Sums

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Special Judge Problem Description A subsum of the sequence is sum of one or more consecutive integers of it. You are given an integer  N ( 1≤N≤2000  ). Your task is to make a sequence of integers which are less than  3(N+6) , such that its all subsums ( N(N+1)/2  in total) are different from each other.   Input There are several test cases. The first line of the input contains an integer  T(1≤T≤200) , the number of test cases. Each of the next  T  lines contains an integer , N  the length of the sequence.   Output For each test case, print one line with  N  space separated integers representing your sequence. If multiple solutions exist, any of them will be accepted.   Sample Input 2 2 5   Sample Output 1 2 1 2 4 8 16 题意：给你一个n，找出一个长度为n的序列，数都为正整数且不超过3*n+18，使得他们的子序列和各不相同。 题解：我是个翻译员23333，具体为什么这样做我也不会QAQ。 翻译：寻找一个素数p刚好大于n，定义s[i]为前i个数的和，再找出一个x，0<=x<p

S[i] = 2 * i * p + (i * (i+1) / 2 * x) % p

定义r[i] = (i * (i+1) / 2 * x) % p.

如果s[i]-s[j]=s[k]-s[l] 那么i-j=k-l 因为|r[i]-r[j]|<p且|r[k]-r[l]|<p

而且(r[i]-r[j]-r[k]+r[l])能被p整除，所以i+j=k+l。

也就是说i=k且j=l

对于所有的6<=n<=2000，我们只要for一下寻找满足每个数都小于3*n+18的x就可以了

然后我们从1for到p-1就行了，不用去管0

ps：朝鲜ACM best ACM 强无敌 这题全场744发没一个队过

#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int s[2005]; int main(){ int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); int i,j,p; for(p=n+1;;p++){ int flag=1; for(j=2;j*j<=p;j++){ if(p%j==0){ flag=0; break; } } if(flag)break; } int x; for(x=1;x<p;x++){ for(i=1;i<=n;i++){ s[i]=2*i*p+(i*(i+1)/2*x)%p; if(s[i]-s[i-1]>=3*n+18)break; } if(i==n+1)break; } for(i=1;i<n;i++){ printf("%d ",s[i]-s[i-1]); } printf("%d\n",s[i]-s[i-1]); } return 0; }