ABCDE略

F

感觉考的是分形。首先画图可以发现，从第0行开始算，二的整数次幂的行中间全是零，并且呈现倒三角的形状蔓延至下面的行而这个倒三角左边和右边的正三角和顶部的正三角完全一致。我们可以先把第n行全部赋值为1，然后判断哪个是0。每一次查询的参数是要判断第n行第l个数到第r个数中哪几个为0，以第几行的数为三角形最顶点，此时就可以找到第n行中哪几个数是属于倒三角的0，然后搜连续的0的左边和右边即可。这里是递归思想。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int T,n,k,a[N];
void init()
{
}
void dfs(int l,int r,int t)
{if(l>=r) return ;int s=1;while(1){if(s*2<=n-t) s*=2;else break;}s++;if(l+(n-(t+s-1)+1)>r-((n-(t+s-1)+1))) return ;for(int i=l+(n-(t+s-1)+1);i<=r-((n-(t+s-1)+1));i++)a[i]=0;dfs(l,l+(n-(t+s-1)+1)-1,s+t-1);dfs(r-((n-(t+s-1)+1))+1,r,s+t-1);
}
void solve()
{cin>>n>>k;init();for(int i=1;i<=n;i++) a[i]=k;dfs(1,n,1);for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
}
signed main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>T;while(T--) solve();
}

G

这题考整除分块

k的范围很大，故考虑按照p的大小分类讨论。

1.n<p<=k，此时rev(n,p)=n，一共有k-n个，总和为(k-n)*n。O(1)即可算出

2.根号(n)<p<=n，此时n的p进制只有两位。n=n1n0=n1*p+n0,n0=n%p，n1=n/p。rev(n,p)=n0*p+n1=p*(n%p)+n/p，有以下公式

第一个式子可以用等差数列，n/p的加和，后面俩个式子枚举p的左端点l可以直接求出n/l=n/r的右端点。

3.p<=根号(n)，只有不到根号(n)个，所以直接模拟即可。把这个数每一位拆出来，注意进制。