专栏文章

2025.2.11模拟赛总结

wwangzilong913
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqa2ga7
此快照首次捕获于
2025/12/04 01:25
3 个月前
此快照最后确认于
2025/12/04 01:25
3 个月前
查看原文
学了数论，整个人都麻了。比赛更是惨不忍睹，600分的题，拿了195分qaq

T1 scrape together

考时20分qaq，还是打表打出来的qwq
题意很简单，就是算由 NN 个 NN 拼在一起的 VNmod   998244353V_{N} \mod\ 998244353 等于多少。
举点例子
当N=5N=5时，VN=55555V_{N}=55555，答案等于 555555555555。
当N=9N=9时，VN=999999999V_{N}=999999999，答案等于 17556461755646。
当N=10000000000N=10000000000 时，VN=V_{N}=……(不想写太多了)，答案等于 468086693468086693 。

解题思路

首先看范围……wc！！！
1≤N≤10181\le N \le 10^{18}
101810^{18} 个 101810^{18} 接在一起，不炸 long longlong\ long 才怪。
所以我们优先砍死出题人(bushi)，优先考虑数学方法。
我们先把 NN 的位数 dd 算出来。
易得原问题变为：
VN=∑i=0n−1N×(10d)i mod 998244353V_{N}=\sum_{i=0}^{n-1}N\times(10^{d})^{i} \ mod \ 998244353 =N×∑i=0n−1(10d)i mod 998244353=N\times\sum_{i=0}^{n-1}(10^{d})^{i} \ mod \ 998244353
可以看出，后半部分是一个公比为 10d10^{d} ，首项为 11 的等比数列
根据等比数列求和公式可知：
∑i=0n−1(10d)i=(10d)N−110d−1\sum_{i=0}^{n-1}(10^{d})^{i}=\frac{(10^{d})^{N}-1}{10^{d}-1}
又因费马小定理：
(10d)N−110d−110d−1≡[(10d)N−1]×(10d−1)998244351  (mod 998244353)\frac{(10^{d})^{N}-1}{10^{d}-110^{d}-1}\equiv[(10^{d})^{N}-1]\times(10^{d}-1)^{998244351} \ \ (mod \ 998244353)
所以我们先把位数 dd 算出来，再用快速幂就可以用 O(logN+loglogN)O(logN+loglogN) 的复杂度完成此题。

danm码 代码环节

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M = 998244353;
int ksm(int a,int b){
	int ans = 1;
	while(b){
		if(b & 1) ans = ans * a % M;
		a = a * a % M;
		b >>= 1;
	}
	return ans;
}

int get_digit(int x){
	int res = 0;
	while(x){
		res++;
		x /= 10;
	}
	return res;
}
signed main(){
	int n;
	cin>>n;
	int d = get_digit(n);
	int a = ksm(10,d);
	int b = ksm(a,n)-1;
	int c = ksm(a-1,M-2);
	cout<<((n%M)*(((b%M)*(c%M))%M))%M;
	return 0;
}

T2 factor

AcWing 97.约数之和
考时90分，没有特判底数为0的情况，没什么好讲的

代码环节

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int ksm(int a,int b,int p){
	int ans = 1;
	while(b){
		if(b & 1) ans = ans * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return ans;
}

int zys[114514],num[114514],cnt;
void fjzys(int n){
	for(int i = 2;i <= n/i;i++){
		if(n % i == 0){
			cnt++;
			zys[cnt] = i;
			num[cnt] = 0;
			while(n % i == 0){
				num[cnt]++;
				n /= i;
			}
		}
	}
	if(n > 1){
		cnt++;
		zys[cnt] = n;
		num[cnt]++;
	}
}

signed main(){
	int a,b,ans = 1;
	cin>>a>>b;
	if(a == 0){
	    cout<<0;
	    return 0;
	}
	fjzys(a);
	for(int i = 1;i <= cnt;i++){
		if((zys[i]-1) % 9901 == 0){
			ans = (b * num[i] + 1) % 9901 * ans % 9901;
			continue;
		}
		int xx = ksm(zys[i],b*num[i]+1,9901);
		int yy = ksm(zys[i] - 1,9901 - 2,9901);
		xx = (xx - 1 + 9901) % 9901;
		ans = ans * xx % 9901 *yy % 9901;
	}
	cout<<ans;
	return 0;
}

T3 calculate

洛谷 P2485 [SDOI2011] 计算器
AcWing 224.计算器
考时65分，扩欧出了亿~~点问题。
首先读题。
要求我们完成三类任务
1.计算 yz mod py^{z} \bmod p
2.求满足 x×y≡z (mod p)x\times y\equiv z \ (mod \ p) 的最小 xx
3.求满足 yx≡z (mod p)y^{x}\equiv z \ (mod \ p) 的最小 xx
其中 1≤y,z,p≤1091\le y,z,p \le 10^{9}，且保证 pp 为素数
边读题我们就可以看出，此题纯考板子。第1个是快速幂，第2个是扩展欧几里得算法求线性同余方程，第3个是BSGS算法(Baby Btep Giant Step算法、大步小步算法)。
只要熟练掌握它们，此题极易。

代码环节

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int ksm(int a,int b,int p){
	int ans = 1;
	while(b){
		if(b & 1) ans = ans * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return ans;
}

int exgcd(int a,int b,int &xx,int &yy){
	if(b == 0){
		xx = 1;
		yy = 0;
		return a;
	}
	int d = exgcd(b,a%b,xx,yy);
	int z = xx;
	xx = yy;
	yy = z - (a/b)*xx;
	return d;
}
int BSGS(int a,int b,int p){
	/*unordered_*/map <int,int> m;
	m.clear();
	b %= p;
	int t = (sqrt(p))+1;
	for(int i = 0;i < t;i++){
		int v = b * ksm(a,i,p) % p;
		m[v] = i;
	}
	a = ksm(a,t,p);
	if(a == 0){
		if(b == 0) return 1;
		else return -114514;
	}
	for(int i = 0;i <= t;i++){
		int v = ksm(a,i,p);
		int j;
		if(m.find(v) == m.end()) j = -114514;
		else j = m[v];
		if(t * i - j>= 0 && j >= 0) return t * i - j;
	}
	return -114514;
}
signed main(){
	int t,k;
	cin>>t>>k;
	if(k == 1){
		while(t--){
			int y,z,p;
			cin>>y>>z>>p;
			cout<<ksm(y,z,p)<<endl;
		}
	}
	if(k == 2){
		while(t--){
			int y,z,p;
			cin>>y>>z>>p;
			int xx,yy,d;
			d = exgcd(y,p,xx,yy);
			if(z % d == 0){
			    int ans = xx * (z/d);
                ans = (ans % (p/d) + (p/d)) % (p/d);
                cout<<ans<<endl;
			}
			else cout<<"Orz, I cannot find x!"<<endl;
		}
	}
	if(k == 3){
		while(t--){
			int y,z,p;
			cin>>y>>z>>p;
			int xx = BSGS(y,z,p);
			if(xx != -114514) cout<<xx<<endl;
			else cout<<"Orz, I cannot find x!"<<endl;
		}
	}
	return 0;
}

T4 SquarePair

洛谷 AT_abc342_d [ABC342D] Square Pair

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...