• 欢迎光临~

# [ARC145] Non Arithmetic Progression Set

### Problem Statement

Construct a set \$S\$ of integers satisfying all of the conditions below. It can be proved that at least one such set \$S\$ exists under the Constraints of this problem.

• \$S\$ has exactly \$N\$ elements.
• The element of \$S\$ are distinct integers between \$-10^7\$ and \$10^7\$ (inclusive).
• \$ displaystyle sum _{s in S} s = M\$.
• \$ y-xneq z-y\$ for every triple \$ x,y,z\$ \$(x < y < z)\$ of distinct elements in \$ S\$.

### Constraints

• \$1 leq N leq 10^4\$
• \$|M| leq Ntimes 10^6\$
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

```\$N\$ \$M\$
```

### Output

Let \$s_1,s_2,ldots,s_N\$ be the elements of \$S\$. Print a set \$S\$ that satisfies the conditions in the following format:

```\$s_1\$ \$s_2\$ \$ldots\$ \$s_N\$
```

If multiple solutions exist, any of them will be accepted.

```3 9
```

### Sample Output 1

```1 2 6
```

We have \$2-1 neq 6-2\$ and \$1+2+6=9\$, so this output satisfies the conditions. Many other solutions exist.

```5 -15
```

### Sample Output 2

```-15 -5 0 2 3
```

\$M\$ may be negative.

(n=5,m=-15)

((0010)_3=3)
((0100)_3=9)
((0110)_3=12)
((1000)_3=27)
((1010)_3=30)

((0011)_3=4)
((0101)_3=10)
((0111)_3=13)
((1001)_3=28)
((1010)_3=30)

\$ {-16,-10,-7,8,10}\$

``````#include<bits/stdc++.h>
const int N=10005;
int n,s[N],ret;
long long m,x,sum,d;
int main()
{
scanf("%d%lld",&n,&m);
for(int i=2;i<=2*n;i+=2)
{
ret=3;
for(int j=1;j<15;j++)
{
if(i>>j&1)
s[i>>1]+=ret;
ret*=3;
}
sum+=s[i>>1];
}
x=((m-sum)%n+n)%n;
d=floor((1.00*m-sum)/n);
for(int i=1;i<=x;i++)
s[i]++;
for(int i=1;i<=n;i++)
printf("%lld ",s[i]+d);
}
``````