官方题解 | COCR 提高赛 #1

MuktorFM

2025-03-01 20:53:17

发布于：云南

156阅读

0回复

0点赞

语雀题解，密码：gfli

COCR 系列竞赛往届题目：题单

繁杂の附魔：模拟

正解

我们只需判断 $a\div2$ 、 $b\div4$ 和 $c$ 的结果最小值即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int T; cin >> T;
    while(T--){
        int a,b,c; cin >> a >> b >> c;
        cout << min(a / 2,min(b / 4,c)) << "\n";
    }
    return 0;
}

时间复杂度： $O(T)$
预计得分： $100pts$

烦人の建交：贪心

正解

贪心策略就是对于同一个亲戚，我们只需要选择时间最少的即可。在处理每个亲戚的时间时，我们可以用 vis 数组记录是否见到过。

#include<bits/stdc++.h>
using namespace std;
struct node{
	int u,dis;
}a[10000005];
bool vis[10000005];
bool cmp(node a,node b){return a.dis < b.dis;}
int main(){
    int n; cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i].u >> a[i].dis;
    sort(a + 1,a + n + 1,cmp);
    long long ans = 0;
    for(int i = 1;i <= n;i++){
    	if(vis[a[i].u] == 0){
        	vis[a[i].u] = 1;
            ans += a[i].dis;
        }
    }
    cout << ans;
    return 0;
}

时间复杂度： $O(N \log N)$
预计得分： $120pts$

石子の游戏：博弈论、dfs枚举

题意简述

输入 $N$ 和 $M$ 表示石子的数量和最多拿取的石子数，输出必胜方和可能出现的拿取方案。

赢家分析

这是一个经典的巴什博弈问题。根据其结论可得：

当 $N \bmod (M+1) = 0$ 时，先手必赢。
当 $N \bmod (M+1) \neq 0$ 时，后手必赢。

由于当先手必胜时，一定会出 $N\bmod (M+1)$ ，使得剩下的石子数量为 $M+1$ 的倍数。

if(n % (m + 1) == 0) cout << "second\n";
else{
  cout << "first\n";
  for(int i = 0;i < v.size();i++) cout << n % (m + 1) << " ";
  cout << "\n";
}

方案数分析

由于必输方可以随意拿取 $1$ 到 $M$ 个石子，所以影响方案数的因素是必输方的拿取方案。我们可以使用排列公式来解决，在排列时记录每种方式。

vector<vector<int>> v;
void dfs(int now,vector<int> path){
    if(now == N + 1){
        v.push_back(path);
        return;
    }
    for(int i = 1;i <= m;i++){
        path.push_back(i);
        dfs(now + 1,path);
        path.pop_back();
    }
}

每一方的拿取方案

由于必胜方需要让自己拿到石子数量与上一轮对方拿的石子数量之和为 $M+1$ ，所以若不计入先手必胜情况中的先手率先拿取的石子数量，轮数为： $N\div(M+1)$ 。

N = n / (m + 1);
for(int i = 0;i < N;i++){
  for(int j = 0;j < v.size();j++) cout << v[j][i] << " ";
  cout << "\n";
  for(int j = 0;j < v.size();j++) cout << m + 1 - v[j][i] << " ";
  cout << "\n";
}

正解

#include<bits/stdc++.h>
#define int long long
using namespace std;
int N,n,m;
vector<vector<int>> v;
void dfs(int now,vector<int> path){
    if(now == N + 1){
        v.push_back(path);
        return;
    }
    for(int i = 1;i <= m;i++){
        path.push_back(i);
        dfs(now + 1,path);
        path.pop_back();
    }
}
signed main(){
    cin >> n >> m;
    N = n / (m + 1);
    vector<int> path;
    dfs(1,path);
    if(n % (m + 1) == 0) cout << "second\n";
    else{
        cout << "first\n";
        for(int i = 0;i < v.size();i++) cout << n % (m + 1) << " ";
        cout << "\n";
    }
    for(int i = 0;i < N;i++){
        for(int j = 0;j < v.size();j++) cout << v[j][i] << " ";
        cout << "\n";
        for(int j = 0;j < v.size();j++) cout << m + 1 - v[j][i] << " ";
        cout << "\n";
    }
    return 0;
}

时间复杂度： $O(M^{\frac{N}{M+1}})$
预计得分： $140pts$

定点の轰炸：ST表、线段树

题意简述

题目描述了一个城市，城市中有 $N$ 座房子，每座房子有一个高度 $h_i$ 。JW 的父亲需要执行 $Q$ 次轰炸任务，每次任务给定一个区间 $[l, r]$ ，要求在这个区间内选择高度最高的房子进行轰炸。如果有多个房子高度相同，选择编号最小的那个。

解题思路

这个问题可以转化为一个经典的区间最大值查询问题。我们需要在给定的区间 $[l, r]$ 内找到高度最大的房子，并返回其编号。由于 $N$ 和 $Q$ 都可能非常大（ $N \leq 3 \times 10^5$ ， $Q \leq 10^6$ ），我们需要一个高效的算法来处理这些查询。

方法选择

暴力法：对于每个查询，遍历区间 $[l, r]$ ，找到最大值。这种方法的时间复杂度是 $O(Q \times N)$ ，显然无法通过。
线段树：线段树可以处理区间查询和更新操作，时间复杂度为 $O(\log N)$ 每次查询。对于 $Q = 10^6$ 来说，总时间复杂度为 $O(Q \log N)$ ，可以通过。
ST表：ST表是一种用于解决静态区间最值查询的数据结构，预处理时间复杂度为 $O(N \log N)$ ，查询时间复杂度为 $O(1)$ 。对于 $Q = 10^6$ 来说，总时间复杂度为 $O(N \log N + Q)$ ，也可以通过。

由于题目中房子高度是静态的（不会改变），ST表是一个非常适合的选择。

预处理

定义： $st[i][j]$ 表示从位置 $i$ 开始，长度为 $2^j$ 的区间内的最大值的位置。
初始化：对于每个 $i$ ， $st[i][0] = i$ ，因为长度为 $1$ 的区间最大值就是它自己。
递推：对于每个 $j$ ，从 $i = 1$ 到 $i = n - 2^j + 1$ ，比较 $st[i][j-1]$ 和 $st[i + 2^{j-1}][j-1]$ 所对应的值，取较大的那个。

查询

对于查询区间 $[l, r]$ ，我们可以找到一个 $k$ ，使得 $2^k \leq r - l + 1 < 2^{k+1}$ 。然后比较 $st[l][k]$ 和 $st[r - 2^k + 1][k]$ 所对应的值，取较大的那个。

正解

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAXN=3e5+35;
int n,q,l,r,len;
int h[MAXN],logs[MAXN],st[MAXN][25];
int main(){
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",h+i);
		st[i][0]=i;
		if(i>=2) logs[i]=logs[i>>1]+1;
	}
	for(int j=1;1<<j<=n;j++){
		for(int i=1;i<=n;i++){
			if(i+(1<<j)-1>n) break;
			if(h[st[i][j-1]]>=h[st[i+(1<<j-1)][j-1]]) st[i][j]=st[i][j-1];
			else st[i][j]=st[i+(1<<j-1)][j-1];
		}
	}
	while(q--){
		scanf("%d %d",&l,&r);
		len=logs[r-l+1];
		if(h[st[l][len]]>=h[st[r-(1<<len)+1][len]]) printf("%d\n",st[l][len]);
		else printf("%d\n",st[r-(1<<len)+1][len]);
	}
	return 0;
}

时间复杂度： $O(N\log N)$
预计得分： $160pts$

重复の任务：线段树、背包dp、高精度

题意简述

一个任务系统，JW 需要完成一系列任务来获得“同祝”。每个任务都有一定的送祝福数量和收到“同祝”数量，且任务的完成会消耗一定的精力。JW 的精力是有限的，我们需要计算在精力用完前，JW 最多能收集到多少个“同祝”。

解题思路

本题具有很明显的背包dp和线段树特征与特性。

任务的计算

对于第 $i$ 个任务， $f(i)$ 表示送祝福数量与收到“同祝”数量的和。
对于第 $1$ 个任务， $f(1)=a_1+b_1+max(a_1,b_1)$ 。
对于第 $i(i≥2)$ ， $f(i)$ 的计算涉及到前 $a_i$ 和 $b_i$ 个任务 $f(j)$ 的和，以及这些任务中 $f(j)$ 的最大值。

背包dp

本题的数据 $k_i$ 的范围较大，所以需要使用优化。（题解采用二进制优化，也可选择单调队列优化）

for(ll i=1;i<=n;i++){
        muls=1;
        while(c[i]>=muls){
            dp[++cnt+n]=mul(dp[i],muls);
            w[cnt+n]=muls*w[i];
            c[i]-=muls;
            muls<<=1;
        }
        if(c[i]){
            dp[++cnt+n]=mul(dp[i],c[i]);
            w[cnt+n]=c[i]*w[i];
        }
    }
    for(ll i=n+1;i<=n+cnt;i++){
        for(ll j=w[0];j>=w[i];j--){
            dpb[j]=maxs(add(dpb[j-w[i]],dp[i]),dpb[j]);
        }
    }

正解

由于数据可能过大，这里使用高精度算法进行加和乘的操作。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lll vector<ll>
#define eb emplace_back
#define pob pop_back
const ll MAXN=1e5+15;
struct node{
	ll l,r;
	lll sum,maxx;
};
ll n,cnt,muls;
ll a[MAXN],b[MAXN],w[MAXN],c[MAXN];
lll dp[MAXN],dpb[MAXN];
node sgt[MAXN<<2];
inline lll to_lll(ll x){
	lll ret;
	while(x){
		ret.eb(x%10);
		x/=10;
	}
	return ret;
}
inline lll maxs(const lll &a,const lll &b){
	if(a.size()^b.size()){
		if(a.size()>b.size()) return a;
		return b;
	}
	for(ll i=a.size()-1;i>=0;i--){
		if(a[i]^b[i]){
			if(a[i]>b[i]) return a;
			return b;
		}
	}
	return a;
}
inline lll relead(lll a){
	while(a.size()>1&&a.back()==0) a.pob();
	return a;
}
inline lll add(const lll &a,const lll &b){
	if(a.size()>b.size()) return add(b,a);
	ll t=0;
	lll c;
	for(ll i=0;i<a.size();i++){
		c.eb((a[i]+b[i]+t)%10);
		t=(a[i]+b[i]+t)/10;
	}
	for(ll i=a.size();i<b.size();i++){
		c.eb((b[i]+t)%10);
		t=(b[i]+t)/10;
	}
	while(t){
		c.eb(t%10);
		t/=10;
	}
	return relead(c);
}
inline lll mul(const lll &a,const ll &b){
    ll t,x=0;
    lll c;
    for(ll i=0;i<a.size();i++){
        t=a[i]*b+x;
        c.eb(t%10);
        x=t/10;
    }
    while(x){
        c.eb(x%10);
        x/=10;
    }
    return relead(c);
}
inline void print(lll a){
	for(ll i=a.size()-1;i>=0;i--) cout<<a[i];
	return;
}
inline ll ls(const ll &p){return p<<1;}
inline ll rs(const ll &p){return p<<1|1;}
inline void build(const ll &l,const ll &r,const ll &p){
	lll t(1,0);
	sgt[p]={l,r,t,t};
	if(l>=r) return;
	ll mid=l+r>>1;
	build(l,mid,ls(p));
	build(mid+1,r,rs(p));
	return;
}
inline void update(const ll &l,const ll &r,const ll &x,const ll &p,const lll &c){
	if(l>=x&&r<=x){
		sgt[p].sum=sgt[p].maxx=c;
		return;
	}
	ll mid=l+r>>1;
	if(mid>=x) update(l,mid,x,ls(p),c);
	if(mid<x) update(mid+1,r,x,rs(p),c);
	sgt[p].sum=add(sgt[ls(p)].sum,sgt[rs(p)].sum);
	sgt[p].maxx=maxs(sgt[ls(p)].maxx,sgt[rs(p)].maxx);
	return;
}
inline lll query(const ll &l,const ll &r,const ll &ql,const ll &qr,const ll &p,const bool &op){
	if(l>=ql&&r<=qr){
		if(op) return sgt[p].sum;
		return sgt[p].maxx;
	}
	ll mid=l+r>>1;
	lll ret;
	if(mid>=ql) ret=query(l,mid,ql,qr,ls(p),op);
	if(mid<qr){
		if(op) ret=add(ret,query(mid+1,r,ql,qr,rs(p),op));
		else ret=maxs(query(mid+1,r,ql,qr,rs(p),op),ret);
	}
	return ret;
}
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++) cin>>a[i];
	for(ll i=1;i<=n;i++) cin>>b[i];
    for(ll i=0;i<=n;i++) cin>>w[i];
    for(ll i=1;i<=n;i++) cin>>c[i];
	build(1,n,1);
	dp[1]=to_lll(a[1]+b[1]+max(a[1],b[1]));
	update(1,n,1,1,dp[1]);
	for(ll i=2;i<=n;i++){
		dp[i]=add(query(1,n,a[i],b[i],1,true),query(1,n,a[i],b[i],1,false));
		update(1,n,i,1,dp[i]);
	}
    for(ll i=1;i<=n;i++){
        muls=1;
        while(c[i]>=muls){
            dp[++cnt+n]=mul(dp[i],muls);
            w[cnt+n]=muls*w[i];
            c[i]-=muls;
            muls<<=1;
        }
        if(c[i]){
            dp[++cnt+n]=mul(dp[i],c[i]);
            w[cnt+n]=c[i]*w[i];
        }
    }
    for(ll i=n+1;i<=n+cnt;i++){
        for(ll j=w[0];j>=w[i];j--){
            dpb[j]=maxs(add(dpb[j-w[i]],dp[i]),dpb[j]);
        }
    }
    print(dpb[w[0]]);
	return 0;
}

时间复杂度： $O(N\log N+N\times w[0])$
预计得分： $180pts$

奇怪の公式：数论、素数筛、矩阵、欧拉定理

题意简述

给出 $f(n,x,y)$ 、 $g_i$ 、 $h(x)$ 的定义，求 $h((\gcd{(g_n,g_{x+y})} \bmod 10^5)!)$ 的值。

公式化简

公式 1

$f_{n,x,y}=(\sum_{0 \le i,2|i}^{n}C_n^i + \sum_{i=0}^{n}(\sum_{j=0}^{n}y^jx^{n-j}C_n^j)C_n^i)\mod 10^9+7$

由引理

$(x+y)^n=\sum_{i=0}^{n}y^ix^{n-i}C_n^i$

带入 $x=1,y=1$ 可得

$\sum_{0 \le i}^{n}C_n^i=\sum_{i=0}^{n}1^i1^{n-i}C_n^i=(1+1)^n=2^n$

同理，带入 $x=1,y=-1$ 可得

$\begin{aligned} (1+(-1))^n \\ =\sum_{i=0}^{n}(-1)^i1^{n-i}C_n^i=0 \\ =\sum_{i=0}^n(-1)^iC_n^i \\ =C_n^0-C_n^1+C_n^2-C_n^3+\cdots+(-1)^nC_n^n \\ \to C_n^0+C_n^2+\cdots =C_n^1+C_n^3+C_n^5+\cdots \\ \to \sum_{0 \le i,2|i}^{n}C_n^i =\sum_{0 \le i,2|(i+1)}^{n}C_n^i \\ \to 2\sum_{0 \le i,2|i}^{n}C_n^i=\sum_{0 \le i}^{n}C_n^i=2^n \\ \to \sum_{0 \le i,2|i}^{n}C_n^i=\frac{2^n}{2}=2^{n-1}\end{aligned}$

$\sum_{j=0}^{n}y^jx^{n-j}C_n^j=(x+y)^n$

$\sum_{i=0}^{n}(\sum_{j=0}^{n}y^jx^{n-j}C_n^j)C_n^i=\sum_{i=0}^{n}(x+y)^nC_n^i=(x+y)^n2^n$

$\begin{aligned} f_{n,x,y}=(\sum_{0 \le i,2|i}^{n}C_n^i + \sum_{i=0}^{n}(\sum_{j=0}^{n}y^jx^{n-j}C_n^j)C_n^i)\mod 10^9+7 \\=(2^{n-1}+2^n(x+y)^n) \mod 10^9+7 \end{aligned}$

可用快速幂解决。

long long pw(long long a,long long b,long long mod) {
    long long ans=1;
    a%=mod;
    while (b){
        if (b&1){
        	ans=ans*a%mod;
		}
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
long long f(long long n, long long x, long long y){
    return ((pw(x+y,n,MOD)*pw(2,n,MOD))%MOD+pw(2,n-1,MOD))%MOD;
}

公式 2

$g_i = \begin{cases} [i = 1] & (i \leq 1) \\ (f_{x,n,x+y}g_{i - 1} + f_{y,x+y,n}g_{i - 2}) \mod 10^9+7& (i \gt 1) \end{cases}$

定义 $p=f_{x,n,x+y},q=f_{y,x+y,n}$
即：

$g_i = \begin{cases} [i = 1] & (i \leq 1) \\ (pg_{i - 1} + qg_{i - 2}) \mod 10^9+7& (i \gt 1) \end{cases}$

容易发现这是斐波那契数列，其初始矩阵为：

$\begin{bmatrix}p & 1 \\ q & 0\end{bmatrix}$

可用矩阵快速幂解决。

struct Mat{
    long long mat[2][2];
    Mat(){
        mat[0][0]=mat[1][1]=1;
        mat[0][1]=mat[1][0]=0;
    }
    Mat operator*(const Mat& ot) const{
        Mat res;
        res.mat[0][0]=(mat[0][0]*ot.mat[0][0]+mat[0][1]*ot.mat[1][0])%MOD;
        res.mat[0][1]=(mat[0][0]*ot.mat[0][1]+mat[0][1]*ot.mat[1][1])%MOD;
        res.mat[1][0]=(mat[1][0]*ot.mat[0][0]+mat[1][1]*ot.mat[1][0])%MOD;
        res.mat[1][1]=(mat[1][0]*ot.mat[0][1]+mat[1][1]*ot.mat[1][1])%MOD;
        return res;
    }
};
Mat mat_pw(Mat a,long long b){
    Mat res;
    while (b) {
        if (b&1){
        	res=res*a;
		}
        a=a*a;
        b>>=1;
    }
    return res;
}
long long fib(long long n){
    if (n==0){
    	return 0;
	}
    Mat base;
    base.mat[0][0]=f(x,n,x+y);
    base.mat[0][1]=f(y,x+y,n);
    base.mat[1][0]=1;
    base.mat[1][1]=0;
    Mat res=mat_pw(base,n-1);
    return res.mat[0][0];
}

公式 3

$h(x)=\sum_{d=1,x|d}^{x}p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1}(0 < p <1)$

$\begin{aligned} p\sum_{1 \le i}^{\infty}i \times p(1-p)^{i-1}(0 < p <1) = p \times p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1} \end{aligned}$

定义

$\begin{aligned} k=p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1}=(1-p)^0+2(1-p)^1+\cdot\cdot\cdot \\ k-(1-p)k=1+2(1-p)+\cdot\cdot\cdot-(1-p)-2(1-p)^2-\cdot\cdot\cdot \\ =1+(1-p)+(1-p)^2+\cdot\cdot\cdot \\ =\sum_{0 \le i}^{\infty}(1-p)^i \\ =\frac{1 \cdot(1-(1-p)^n)}{1-(1-p)}(n \to \infty) \\ = \frac{1-(1-p)^n}{p}(n \to \infty) \end{aligned}$

因为：

$0<p<1 \to 0<(1-p)<1$

所以：

$(1-p)^n(n \to \infty)=a^n(0<a<1)(n \to \infty) \to 0$

$k-(1-p)k=k-(k-pk)=k-k+pk=pk=\sum_{0 \le i}^{\infty}(1-p)^i = \frac{1}{p} \to k=\frac{1}{p^2}$

即：

$p\sum_{1 \le i}^{\infty}i \times p(1-p)^{i-1}(0 < p <1) = p \times k =p \times \frac{1}{p^2}=\frac{1}{p}$

$p \times p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1} =p \times \frac{1}{p}=1$

$h(x)=\sum_{d=1,x|d}^{x}p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1}(0 < p <1)=\sum_{d=1,x|d}^{x}k^2(k=1)=\tau{(x)}$

由引理

$\tau{(x)}=\prod_{p \le x} (\sum_{k=1}^{\infty}\left(\lfloor\dfrac{x}{p^k}\rfloor\right)+1)(p \in \text{Prime})$

可得

$h(x!)=\prod_{p \le x!} (\sum_{k=1}^{\infty}\left(\lfloor\dfrac{x!}{p^k}\rfloor\right)+1)(p \in \text{Prime})$

long long g(long long i,long long x,long long y) {
    if (i<=1){
        long long fi=f(i,x,y);
        long long fx=f(x,i,y-1);
        long long pff=pw(fi,fx,MOD);
        return pff;
    }
    return fib(i);
}

计算结果

$\gcd{(g_n,g_{x+y})}$

由引理得：

$\gcd{(g_n,g_{x+y})}=g_{\gcd{(n,x+y)}}$

易得：

$h((\gcd{(g_n,g_{x+y})} \mod 10^5)!) \to h(x!)(x=\gcd{(g_n,g_{x+y})} \mod 10^5)$

$x$ 可 $O(log _2{(\max{(n,x+y)})})$ 得出， $h(x!)$ 可用素数筛 $O(x)(x < 10^5)$ 解决

vector<int> p;
bool vis[1000010];
void init(){
    memset(vis,1,sizeof vis);
    vis[0]=vis[1]=0;
    for (int i=2;i<1000010;i++) {
        if (vis[i]){
            p.push_back(i);
            for (int j=2*i;j<1000010;j+=i) {
                vis[j]=0;
            }
        }
    }
}

正解

#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
long long n,x,y;
long long pw(long long a,long long b,long long mod) {
    long long ans=1;
    a%=mod;
    while (b){
        if (b&1){
        	ans=ans*a%mod;
		}
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
long long f(long long n, long long x, long long y){
    return ((pw(x+y,n,MOD)*pw(2,n,MOD))%MOD+pw(2,n-1,MOD))%MOD;
}
struct Mat{
    long long mat[2][2];
    Mat(){
        mat[0][0]=mat[1][1]=1;
        mat[0][1]=mat[1][0]=0;
    }
    Mat operator*(const Mat& ot) const{
        Mat res;
        res.mat[0][0]=(mat[0][0]*ot.mat[0][0]+mat[0][1]*ot.mat[1][0])%MOD;
        res.mat[0][1]=(mat[0][0]*ot.mat[0][1]+mat[0][1]*ot.mat[1][1])%MOD;
        res.mat[1][0]=(mat[1][0]*ot.mat[0][0]+mat[1][1]*ot.mat[1][0])%MOD;
        res.mat[1][1]=(mat[1][0]*ot.mat[0][1]+mat[1][1]*ot.mat[1][1])%MOD;
        return res;
    }
};
Mat mat_pw(Mat a,long long b){
    Mat res;
    while (b) {
        if (b&1){
        	res=res*a;
		}
        a=a*a;
        b>>=1;
    }
    return res;
}
long long fib(long long n){
    if (n==0){
    	return 0;
	}
    Mat base;
    base.mat[0][0]=f(x,n,x+y);
    base.mat[0][1]=f(y,x+y,n);
    base.mat[1][0]=1;
    base.mat[1][1]=0;
    Mat res=mat_pw(base,n-1);
    return res.mat[0][0];
}
long long g(long long i,long long x,long long y) {
    if (i<=1){
        long long fi=f(i,x,y);
        long long fx=f(x,i,y-1);
        long long pff=pw(fi,fx,MOD);
        return pff;
    }
    return fib(i);
}
vector<int> p;
bool vis[1000010];
void init(){
    memset(vis,1,sizeof vis);
    vis[0]=vis[1]=0;
    for (int i=2;i<1000010;i++) {
        if (vis[i]){
            p.push_back(i);
            for (int j=2*i;j<1000010;j+=i) {
                vis[j]=0;
            }
        }
    }
}
long long cd(long long x){
    long long ans=1;
    for (int ps:p){
        long long et=0;
        long long pr=ps;
        while (pr<=x){
            et+=x/pr;
            if (pr>x/ps){
				break;
			}
            pr*=ps;
        }
        ans=(ans*(et+1))%MOD;
    }
    return ans;
}
int main() {
    init();
    cin>>n>>x>>y;
    long long gnxy=__gcd(n,x+y);
    long long gg=g(gnxy,x,y);
    long long gm=gg%(100000);
    long long phi=cd(gm);
    cout<<phi<<endl;
    return 0;
}

时间复杂度： $O(Mod)$ ，其中 $Mod\le10^5$
预计得分： $200pts$

有帮助，赞一个

去预览

0/2000

全部评论 14

亚洲卷王 AK IOI
%%%神仙T6

2025-03-01 来自北京
1
李总（不加团队）
顶

2025-03-01 来自四川
1
十二
没优化前的代码量不得过150

2025-03-03 来自广东
0
- MuktorFM
  回复十二
  啥玩意
  
  2025-03-03 来自云南
  0
- 十二
  回复MuktorFM
  第5题和第6题
  
  2025-03-03 来自广东
  0
- MuktorFM
  回复十二
  没有这个规定的啊
  
  2025-03-03 来自云南
  0
cmp
顶

2025-03-02 来自广东
0
egogaming
md真的要高精

2025-03-01 来自广东
0
- egogaming
  回复egogaming
  不会python崩了
  
  2025-03-02 来自广东
  0
xueman
题解h(x)和题目h(x)的定义不一样？题解为啥少个p

2025-03-01 来自山东
0
- MuktorFM
  回复xueman
  p可以被化简
  
  2025-03-01 来自云南
  0
- xueman
  回复xueman
  还有题解的h(x)的第二个求和符号后的（1-p）是i-1次，而题目的h（x）的的第二个求和符号是i次
  
  2025-03-01 来自山东
  0
- xueman
  回复MuktorFM
  那求和里面的次数不一样怎么解决
  
  2025-03-01 来自山东
  0
宋雨琦的狗
真是难死人不偿命

2025-03-01 来自天津
0
cjdstttttt
T5 Python大法不需要高精度，线段树直接秒

2025-03-01 来自广东
0
- MuktorFM
  回复cjdstttttt
  T5基本上都是py过的
  
  2025-03-01 来自云南
  0
- cjdstttttt
  回复cjdstttttt
  只需要背个背包板子就行，计算直接暴力
  
  2025-03-01 来自广东
  0
Gragher
窝嘞个超级T6

2025-03-01 来自浙江
0
183****1200
还有就算T5要用高精以及逆天T6

2025-03-01 来自浙江
0
183****1200
还有T4我只用了st表，不知道是不是正解

2025-03-01 来自浙江
0
- MuktorFM
  回复183****1200
  无论如何，AC即可
  
  2025-03-01 来自云南
  0
- cjdstttttt
  回复183****1200
  正解就是ST表
  
  2025-03-01 来自广东
  0
- 183****1200
  回复cjdstttttt
  但我没用线段树
  
  2025-03-02 来自浙江
  0
183****1200
T2我是 $O(n)$ 的

2025-03-01 来自浙江
0
CK七星松|再发团队邀请建议趋势
顶

2025-03-01 来自浙江
0
L.
d
第一

2025-03-01 来自浙江
0