数论，高斯消元，线性基

用户头像 发布于 2025-08-18 98 次阅读 OI

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

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

需要的前置知识：设一个 $B$ 进制数为 $x$，数位和为 $f(x)$，那么：
$$
x \equiv f(x) (\bmod B-1)
$$
证明：
$$
\begin{align}
设x&=\sum_{i=0}^{n}a_i·B^i \\
\because x&=\sum_{i=0}^{n}a_i+a_i·(B^i-1) \\
\therefore x&=\sum_{i=0}^{n}a_i+a_i·(B-1)·(\sum_{j=0}^{i-1}a^{j}) \\
& 又 a_i·(B-1)·(\sum_{j=0}^{i-1}a^{j}) \equiv 0 & \\
& \therefore x \equiv \sum_{i=0}^{n}a_i &
\end{align}
$$

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

#include<bits/stdc++.h>
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<b;i++) cin>>a[i],s+=a[i]*i;
    if(s%(b-1)) a[s%(b-1)]--;
    for(int i=1;i<b;i++) a[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<<ans<<endl;
    }
    return 0;
}
C++

B. 放入糖果

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

#include<bits/stdc++.h>
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<n;i++) cin>>a[i];
    for(int i=1;i<=k;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) cout<<s[k];
    else{
        int q=tag[s[t]%n];
        cout<<s[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 <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n,f,ans;
int a[N];
vector<int> 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<N;i++) t[i].clear();
    	for(int i=2;i<=n;i++) cin>>f,t[f].push_back(i);
    	for(int i=1;i<=n;i++) cin>>a[i];
    	dfs(1,0);
    	cout<<ans<<endl;
    }
    return 0;
}
C++

E. 密码箱

题意可以简化为找到一个数 $x$ 满足：
$$
\begin{align}
x^2 &\equiv 1 (\bmod n), x\in[0,n) \\
\therefore x^2-1 &\equiv 0 \\
(x+1)(x-1) &\equiv 0 \\
\therefore (x+1)(x-1)&=n·k
\end{align}
$$
设有 $a,b$ 满足
$$
a·b=n \land a|(x-1) \land b|(x+1)
$$
枚举因数即可。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,idx;
int ans[10000005];
signed main(){
    cin>>n;
    for(int i=1;i*i<=n;i++) if(n%i==0){
        int a=i,b=n/i;
        for(int j=0;j<=n;j+=b) if((j-2)%a==0&&j-1>=0) ans[++idx]=j-1;
        for(int j=0;j<=n;j+=b) if((j+2)%a==0&&j+1<n) ans[++idx]=j+1;
    }
    sort(ans+1,ans+1+idx);
    idx=unique(ans+1,ans+1+idx)-ans-1;
    for(int i=1;i<=idx;i++) cout<<ans[i]<<endl;
    return 0;
}
C++

F. 余数之和

$$
\begin{align}
&\sum_{i=1}^{n}k \bmod i \\
=&\sum_{i=1}^{n}k-i·\lfloor \frac{k}{i} \rfloor \\
=&n·k-\sum_{i=1}^{n} \sum_{j=1}^{k} i·(\lfloor \frac{j}{i} \rfloor - \lfloor \frac{j-1}{i} \rfloor) \\
=&n·k-\sum_{j=1}^{k} \sum_{i=1}^{n} i·[i|j] \\
=&n·k-\sum_{j=1}^{k} \sigma (j)
\end{align}
$$
对于正因数和的前缀和，
分块计算每一段贡献为 $\lfloor \frac{k}{i} \rfloor$ 的区间的总贡献即可。
代码：

#include<bits/stdc++.h>
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<=n){
    	int t=k/l,r=(t==0?n:min(k/t,n));
    	ans-=(l+r)*(r-l+1)/2*t;
    	l=r+1;
  	}
  	cout<<ans;
  	return 0;
}
C++

J. 线性基1

线性基模板，代码：

#include <bits/stdc++.h>
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<<b.check();
    return 0;
}
C++