S+数论，高斯消元，线性基

A. B进制数与B-1倍数查询问题

需要的前置知识：设一个 $B$ 进制数为 $x$，数位和为 $f\left(x\right)$，那么： $$x\equiv f\left(x\right)(\text{[PARSE ERROR: Undefined("Command("bmod")")]}B-1)$$ 证明： $$\begin{array}{ll}\mathrm{设}x& amp;=\sum _{i=0}^n{a}_i\mathrm{·}{B}^i\\ \mathrm{\because }x& amp;=\sum _{i=0}^n{a}_i+a_i\mathrm{·}(B^i-1)\\ \mathrm{\therefore }x& amp;=\sum _{i=0}^n{a}_i+a_i\mathrm{·}(B-1)\mathrm{·}\left(\sum _{j=0}^{i-1}{a}^j\right)\\ & amp;\mathrm{又}{a}_i\mathrm{·}(B-1)\mathrm{·}\left(\sum _{j=0}^{i-1}{a}^j\right)\equiv 0& amp;\\ & amp;\mathrm{\therefore }x\equiv \sum _{i=0}^n{a}_i& amp;\end{array}$$

由此得证。 根据这一点，为了使这个数足够大，首先肯定要更多的数位， 所以我们减去一个 $sum\text{[PARSE ERROR: Undefined("Command("bmod")")]}(b-1)$， 最后在前缀和数组中二分查找 $k$ 即可。 代码：

#include
using namespace std;
#define int long long
const int N=1e6+5;
int b,q,k,s;
int a[N];
signed main(){
    cin>>b>>q;
    for(int i=0;i>a[i],s+=a[i]*i;
    if(s%(b-1)) a[s%(b-1)]--;
    for(int i=1;i>k,k++;
        int ans=lower_bound(a,a+b,k)-a;
        if(ans==b) cout

`#include
using namespace std;
#define int long long
const int N=1e6+5;
int b,q,k,s;
int a[N];
signed main(){
    cin>>b>>q;
    for(int i=0;i>a[i],s+=a[i]*i;
    if(s%(b-1)) a[s%(b-1)]--;
    for(int i=1;ia[i]+=a[i-1];
    while(q--){
        cin>>k,k++;
        int ans=lower_bound(a,a+b,k)-a;
        if(ans==b) cout"-1\n";
        else cout
    }
    return 0;
}`

C++

B. 放入糖果

这题先模拟，直到找到了一个周期，就可以直接统计答案。 代码还是比较好写的：

#include
using namespace std;
#define int long long
const int N=2e5+5;
int n,k,t;
int a[N],s[N],tag[N];
signed main(){
    memset(tag,-1,sizeof tag);
    cin>>n>>k;
    for(int i=0;i>a[i];
    for(int i=1;i

`#include
using namespace std;
#define int long long
const int N=2e5+5;
int n,k,t;
int a[N],s[N],tag[N];
signed main(){
    memset(tag,-1,sizeof tag);
    cin>>n>>k;
    for(int i=0;i>a[i];
    for(int i=1;i
        s[i]=s[i-1]+a[s[i-1]%n];
        if(tag[s[i-1]%n]!=-1){
            t=i-1;
            break;
        }
        tag[s[i-1]%n]=i;
    }
    if(t==0) couts[k];
    else{
        int q=tag[s[t]%n];
        couts[q-1]+(s[t]-s[q-1])*((k-q+1)/(t-q+1))+(s[q-1+(k-q+1)%(t-q+1)]-s[q-1]);
    }
    return 0;
}`

C++

D. 充实

这道题需要证明一个结论： 若存在一条从根节点到叶子节点的路径使点权的最大公倍数是 $2$ 的幂，答案就加一，
可惜我不会证明。 代码如下：

#include 
using namespace std;
const int N=1e5+5;
int T,n,f,ans;
int a[N];
vector t[N];
void dfs(int u,int x){
	if(!t[u].size()) ans+=!(x&x-1);
	else for(int v:t[u]) dfs(v,__gcd(x,a[v]-a[u]));
}
main(){
    cin>>T;
    while(T--){
    	cin>>n,ans=0;
    	for(int i=0;i>f,t[f].push_back(i);
    	for(int i=1;i>a[i];
    	dfs(1,0);
    	cout

`#include 
using namespace std;
const int N=1e5+5;
int T,n,f,ans;
int a[N];
vectorint> t[N];
void dfs(int u,int x){
	if(!t[u].size()) ans+=!(x&x-1);
	else for(int v:t[u]) dfs(v,__gcd(x,a[v]-a[u]));
}
main(){
    cin>>T;
    while(T--){
    	cin>>n,ans=0;
    	for(int i=0;it[i].clear();
    	for(int i=2;i>f,t[f].push_back(i);
    	for(int i=1;i>a[i];
    	dfs(1,0);
    	cout
    }
    return 0;
}`

C++

E. 密码箱

题意可以简化为找到一个数 $x$ 满足： $$\begin{array}{ll}{x}^2& amp;\equiv 1\left(\text{[PARSE ERROR: Undefined("Command("bmod")")]}n\right),x\in [0,n)\\ \mathrm{\therefore }{x}^2-1& amp;\equiv 0\\ (x+1)(x-1)& amp;\equiv 0\\ \mathrm{\therefore }(x+1)(x-1)& amp;=n\mathrm{·}k\end{array}$$ 设有 $a,b$ 满足 $$a\mathrm{·}b=n\wedge a\left|\right(x-1)\wedge b|(x+1)$$ 枚举因数即可。 代码：

#include
using namespace std;
#define int long long
int n,idx;
int ans[10000005];
signed main(){
    cin>>n;
    for(int i=1;i*i=0) ans[++idx]=j-1;
        for(int j=0;j

`#include
using namespace std;
#define int long long
int n,idx;
int ans[10000005];
signed main(){
    cin>>n;
    for(int i=1;i*iif(n%i==0){
        int a=i,b=n/i;
        for(int j=0;jif((j-2)%a==0&&j-1>=0) ans[++idx]=j-1;
        for(int j=0;jif((j+2)%a==0&&j+1ans[++idx]=j+1;
    }
    sort(ans+1,ans+1+idx);
    idx=unique(ans+1,ans+1+idx)-ans-1;
    for(int i=1;ians[i]
    return 0;
}`

C++

F. 余数之和

$$\begin{array}{ll}& amp;\sum _{i=1}^{n}k\text{[PARSE ERROR: Undefined("Command("bmod")")]}i\\ =& amp;\sum _{i=1}^{n}k-i\mathrm{·}\lfloor \frac{k}{i}\rfloor \\ =& amp;n\mathrm{·}k-\sum _{i=1}^n\sum _{j=1}^{k}i\mathrm{·}(\lfloor \frac{j}{i}\rfloor -\lfloor \frac{j-1}{i}\rfloor )\\ =& amp;n\mathrm{·}k-\sum _{j=1}^k\sum _{i=1}^{n}i\mathrm{·}\left[i\right|j]\\ =& amp;n\mathrm{·}k-\sum _{j=1}^k\sigma \left(j\right)\end{array}$$ 对于正因数和的前缀和， 分块计算每一段贡献为 $\lfloor \frac{k}{i}\rfloor$ 的区间的总贡献即可。 代码：

#include
using namespace std;
#define int long long
int n,k;
signed main(){
    cin>>n>>k;
    int l=1,ans=n*k;
    n=min(n,k); 
    while(l

`#include
using namespace std;
#define int long long
int n,k;
signed main(){
    cin>>n>>k;
    int l=1,ans=n*k;
    n=min(n,k); 
    while(l
    	int t=k/l,r=(t==0?n:min(k/t,n));
    	ans-=(l+r)*(r-l+1)/2*t;
    	l=r+1;
  	}
  	cout
  	return 0;
}`

C++

J. 线性基1

线性基模板，代码：

#include 
using namespace std;
#define int long long
const int N=1e5+5;
int n;
struct basis{
	int p[100];
	void insert(int a){
		for(int i=50;i>=0;i--) if((a>>i)&1){
			if(!p[i]){
				p[i]=a;
				break;
			}
			a^=p[i];
		}
	}
	int check(){
		int ans=0;
		for(int i=63;i>=0;i--) ans=max(ans,ans^p[i]);
		return ans;
	}
}b;
main(){
    cin>>n;
    while(n--){
    	int x;
    	cin>>x;
    	b.insert(x);
    }
    cout

`#include 
using namespace std;
#define int long long
const int N=1e5+5;
int n;
struct basis{
	int p[100];
	void insert(int a){
		for(int i=50;i>=0;i--) if((a>>i)&1){
			if(!p[i]){
				p[i]=a;
				break;
			}
			a^=p[i];
		}
	}
	int check(){
		int ans=0;
		for(int i=63;i>=0;i--) ans=max(ans,ans^p[i]);
		return ans;
	}
}b;
main(){
    cin>>n;
    while(n--){
    	int x;
    	cin>>x;
    	b.insert(x);
    }
    coutb.check();
    return 0;
}`

C++