#P18680. Completely Multiplicative Function

    ID: 18016 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-序列构造奇偶性分析线性筛最小质因子预处理排序贪心全子集枚举一维前缀和0/1 背包倒序更新避免重复使用路径恢复

Completely Multiplicative Function

Completely Multiplicative Function

完全积性函数是一个定义在正整数上的算术函数,满足 f(1)=1f(1)=1,并且对于任意正整数 a,ba,b,都有

f(ab)=f(a)f(b).f(ab)=f(a)f(b).

小青鱼非常喜欢完全积性函数这个概念。他希望找到一个函数 f:N→{−1,1}f:\mathbb N\to\{-1,1\},使得 1≤i≤n1\le i\le n 的所有 f(i)f(i) 的和恰好等于给定整数 kk。

形式化地,你需要找到满足以下条件的函数:

  • 对每个正整数 xx,f(x)∈{−1,1}f(x)\in\{-1,1\};
  • f(1)=1f(1)=1,对任意正整数 x,yx,y,f(x)f(y)=f(xy)f(x)f(y)=f(xy);
  • f(1)+f(2)+⋯+f(n)=kf(1)+f(2)+\cdots+f(n)=k。

这里 x,yx,y 不要求互素。为了检验你是否真正理解了完全积性函数的美,小青鱼请你找出这样一个函数。

输入格式

输入包含多组测试数据。第一行包含一个整数 TT(1≤T≤1051\le T\le10^5),表示测试数据组数。

每组测试数据占一行,包含两个整数 n,kn,k,满足 1≤n≤1061\le n\le10^6、0≤k≤n0\le k\le n。

保证一个输入文件内所有测试数据的 nn 之和不超过 2×1062\times10^6。

输出格式

对每组测试数据:

  • 如果不存在符合条件的函数,输出一行一个整数 -1;
  • 否则,输出一行 nn 个以空格分隔的整数 f(1),f(2),…,f(n)f(1),f(2),\ldots,f(n)。每个数必须为 11 或 −1-1,这些值的和必须恰好为 kk,并且它们必须来自一个满足上述定义的完全积性函数。

如果有多种解,可以输出任意一种。

样例输入

4
4 2
10 0
10 1
10 10

样例输出

1 -1 1 1
1 -1 -1 1 1 1 -1 -1 1 -1
-1
1 1 1 1 1 1 1 1 1 1