本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-06 21:20:54
A
题意
思路
设青蛙出发点为 $m1$ 和 $n1$ ，分别能跳 $m$ 米和 $n$ 米，周长为 $l$，不难发现：
$$x(m-n)\equiv m1-n1 \ ( \bmod \ l )$$
移项得：
$$x(m-n)+ly= m1-n1$$
不妨设 $a=m-n$，$b=l$，$c=m1-n1$
得：
$$ax+by=c$$
若该方程有解，则 $\gcd(a,b) \mid c$ 是必要条件。
可以用exgcd求解。(注意要处理负数的情况)
代码
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return a;
}
d=exgcd(b,a%b,x,y);
int xx=x;
x=y;
y=xx-(a\/b)*y;
return d;
}
signed main(){
\/\/ freopen("road.in","r",stdin);
\/\/ freopen("road.out","w",stdout);
int x,y,m,n,l;
cin>>x>>y>>m>>n>>l;
if(n<m){
swap(n,m);
swap(x,y);
}
int a=x-y;
int b=n-m;
int t=exgcd(b,l,x,y);
\/\/ cout<<a<<' '<<b<<' '<<c<<' '<<t<<endl;
if(a%t){
cout<<"Impossible";
return 0;
}
int md=l\/t;
x=(x*(a\/d)%md+md)%md;
cout<<x;
return 0;
}
B
题意
思路
比较板子。
由题意得：
$$\left\{\begin{matrix} & n-a_1 \equiv 0 \ \pmod{b_1} \ & n-a_2 \equiv 0 \ \pmod{b_2} \ & \dotsb \ & n-a_k \equiv 0 \ \pmod{b_k} \end{matrix}\right.$$
移项得：
$$\left\{\begin{matrix} & n \equiv a_1 \ \pmod{b_1} \ & n \equiv a_2 \ \pmod{b_2} \ & \dotsb \ & n \equiv a_k\ \pmod{b_k} \end{matrix}\right.$$
中国剩余定理板子。
注意这道题要预处理负数的情况并且使用快速乘。
代码
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return a;
}
d=exgcd(b,a%b,x,y);
int xx=x;
x=y;
y=xx-(a\/b)*y;
return d;
}
long long ksm(long long a,long long b){
long long res=0;
while(b>0){
if(b&1)
res=(res+a+lcm)%lcm;
a=(a+a)%lcm;
b>>=1;
}
return res%lcm;
}
int crt(){
int ans=0,mi,x,y,d;
for(int i=1;i<=n;i++){
mi=lcm\/b[i];
exgcd(mi,b[i],x,y);
x=(x%b[i]+b[i])%b[i];
ans=((ans+ksm(mi,ksm(x,a[i])))%lcm+lcm)%lcm;
\/\/ ans=(ans+(mi*x*b[i])%lcm+lcm%lcm)%lcm;
}
return (ans+lcm)%lcm;
}
signed main(){
\/\/ freopen("road.in","r",stdin);
\/\/ freopen("road.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
lcm*=b[i];
}
for(int i=1;i<=n;i++){
a[i]=(a[i]%b[i]+b[i])%b[i];
}
cout<<crt();
return 0;
}
C
题意
P2398加强版。
思路
此题与P2398只相差一点，即求和时求的是 $\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)^2$。
因为P2398中，我们钦定 $\gcd=i$，所以此题仅需将 $i$ 更改为 $i^2$。
代码
void Pr(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(st[i]==0){
cnt++;
prime[cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&prime[j]*i<=n;j++){
st[prime[j]*i]=1;
if(i%prime[j]==0) {
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
signed main(){
\/\/ freopen("inq.in","r",stdin);
\/\/ freopen("inq.out","w",stdout);
cin>>n;
Pr();
for(int i=1;i<=n;i++){
s[i]=(s[i-1]+phi[i])%mod;
\/\/cout<<s[i]<<' ';
}
\/\/Endl
int ans=0;
for(int i=1;i<=n;i++){
ans+=(2*s[n\/i]-1)*i*i%mod;
}
cout<<ans%mod;
return 0;
\/\/ fclose(stdin);
\/\/ fclose(stdout);
}
D
题意
E
题意
思路
不难发现，选出的集合的大小不会大于3。
证：
当 $x=1$ 时，答案显然。
当 $x=2$ 时，答案显然。
当 $x=3$ 时，设三个数分别为 $x1$，$x2$，$x3$。
设 $x1-x2=2^{k1}$，$x2-x3=2^{k2}$，则$x1-x3=2^{k1}+2^{k2}$。
显然，当 $k1=k2$ 时，$2^{k1}+2^{k2}=2^{k3}$。
当 $x=4$ 时，设四个数分别为 $x1$，$x2$，$x3$，$x4$。
设 $x1-x2=2^{k1}$，$x2-x3=2^{k2}$，$x3-x4=2^{k3}$。
根据上述结论不难发现，$k1=k2=k3$。
那么，$x1-x4=3*2^{k1}$，显然不是 $2^k$。
当 $x>4$ 时，该集合定有一个子集长度为4。
根据上述结论，当$x \le 3$ 时，集合可能符合要求。
可以分讨+二分。
具体见代码。
代码
signed main(){
\/\/ freopen("inq.in","r",stdin);
\/\/ freopen("inq.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
for(int i=2;i<n;i++){\/\/枚举第二个数
for(int j=0;j<=30;j++){
int l=lower_bound(a+1,a+i,a[i]-(1<<j))-a;\/\/二分查找
int r=lower_bound(a+i+1,a+1+n,a[i]+(1<<j))-a;
if(a[l]+(1<<j)==a[i]&&a[i]+(1<<j)==a[r]){\/\/如果查找出来的数符合要求
cout<<3<<endl;
cout<<a[l]<<' '<<a[i]<<' '<<a[r];
return 0;
}
}
}
for(int i=2;i<=n;i++){\/\/同上
for(int j=0;j<=30;j++){
int l=lower_bound(a+1,a+i,a[i]-(1<<j))-a;
if(a[l]+(1<<j)==a[i]){
cout<<2<<endl;
cout<<a[l]<<' '<<a[i];
return 0;
}
}
}
cout<<1<<endl<<a[1];
return 0;
\/\/ fclose(stdin);
\/\/ fclose(stdout);
}
F
题意
用 $n$ 张纸币（1,5,10,50）能组成多少种不同的面值和？
$n\le 1e9$
思路
纯诈骗。
先DFS出 $n\le11$ 的情况，$n>11$ 时，进行差分，不难发现差分均为49.
代码
signed main(){
\/\/ freopen("inq.in","r",stdin);
\/\/ freopen("inq.out","w",stdout);
cin>>n;
if(n<=11) cout<<mny[n];\/\/自己算
else cout<<mny[11]+49*(n-11);
return 0;
\/\/ fclose(stdin);
\/\/ fclose(stdout);
}
G
题意
思路
对 $k$ 进行分讨。
当 $k$ 为偶数，则枚举直径的中间点，以该点为起点查找其他点与该点距离 $\le k/2$ 的点。
当 $k$ 为奇数，则枚举直径的中间边，以该边的两个端点分别为起点查找其他点与该点距离 $\le k/2$ 的点。
代码
void dfs(int x,int len,int fa){
vis[x]=1;
cnt++;
if(len==0) return ;
for(int i=0;i<ve[x].size();i++){
int v=ve[x][i];
if(v==fa) continue;
if(vis[v]) continue;
dfs(v,len-1,x);
}
}
signed main(){
\/\/ freopen("inq.in","r",stdin);
\/\/ freopen("inq.out","w",stdout);
int maxx=0;
cin>>n>>len;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
ve[u].push_back(v);
ve[v].push_back(u);
}
if(len%2==0){
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
cnt=0;
dfs(i,len\/2,0);
maxx=max(maxx,cnt);
}
}
else{
for(int i=1;i<=n;i++){
for(int j=0;j<ve[i].size();j++){
memset(vis,0,sizeof(vis));
int v=ve[i][j];
cnt=0;
dfs(i,len\/2,v);
dfs(v,len\/2,i);
maxx=max(maxx,cnt);
}
}
}
cout<<maxx;
return 0;
\/\/ fclose(stdin);
\/\/ fclose(stdout);
}
鲁ICP备2025150228号