2025.2.11模拟赛总结

· · 个人记录

学了数论，整个人都麻了。比赛更是惨不忍睹，600分的题，拿了195分qaq

T1 scrape together

考时20分qaq，还是打表打出来的qwq

题意很简单，就是算由 N 个 N 拼在一起的 V_{N} \mod\ 998244353 等于多少。

举点例子

当N=5时，V_{N}=55555，答案等于 555555。

当N=9时，V_{N}=999999999，答案等于 1755646。

当$N=10000000000

$。 ## 解题思路 首先看范围……**wc！！！** $1\le N \le 10^{18} 所以我们~~优先砍死出题人(bushi)~~，优先考虑数学方法。 我们先把 $N$ 的位数 $d$ 算出来。 易得原问题变为： $$ V_{N}=\sum_{i=0}^{n-1}N\times(10^{d})^{i} \ mod \ 998244353 $$ $$ =N\times\sum_{i=0}^{n-1}(10^{d})^{i} \ mod \ 998244353 $$ 可以看出，后半部分是一个公比为 $10^{d}$ ，首项为 $1$ 的等比数列 根据等比数列求和公式可知： $$ \sum_{i=0}^{n-1}(10^{d})^{i}=\frac{(10^{d})^{N}-1}{10^{d}-1} $$ 又因费马小定理： $$ \frac{(10^{d})^{N}-1}{10^{d}-110^{d}-1}\equiv[(10^{d})^{N}-1]\times(10^{d}-1)^{998244351} \ \ (mod \ 998244353) $$ 所以我们先把位数 $d$ 算出来，再用快速幂就可以用 $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.约数之和](https://www.acwing.com/problem/content/99/) 考时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] 计算器](https://www.luogu.com.cn/problem/P2485) [AcWing 224.计算器](https://www.acwing.com/problem/content/226/) 考时65分，扩欧出了亿~~点问题。 首先读题。 要求我们完成三类任务 1.计算 $y^{z} \bmod p

2.求满足 x\times y\equiv z \ (mod \ p) 的最小 x

3.求满足 y^{x}\equiv z \ (mod \ p) 的最小 x

其中 1\le y,z,p \le 10^{9}，且保证 p 为素数

边读题我们就可以看出，此题纯考板子。第1个是快速幂，第2个是扩展欧几里得算法求线性同余方程，第3个是BSGS算法(Baby Btep Giant Step算法、大步小步算法)。

只要熟练掌握它们，此题极易。

代码环节

#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