算法竞赛入门【码蹄集进阶塔335题】(MT2276-2280)

2023-11-02 03:30

本文主要是介绍算法竞赛入门【码蹄集进阶塔335题】(MT2276-2280),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法竞赛入门【码蹄集进阶塔335题】(MT2276-2280)


文章目录

  • 算法竞赛入门【码蹄集进阶塔335题】(MT2276-2280)
  • 前言
      • 为什么突然想学算法了?
      • 为什么选择码蹄集作为刷题软件?
  • 目录
    • 1. MT2276 数的自我
    • 2. MT2277 分数个数
    • 3. MT2278 欧拉函数
    • 4. MT2279 欧拉函数2
    • 5. MT2280 数字游戏
    • 结语


前言

在这里插入图片描述

为什么突然想学算法了?

> 用较为“官方”的语言讲,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言,是因为当下快到了考研和找工作的年纪(ಥ_ಥ),无论走哪一条路,都不免需要一些相对丰富的算法知识,是故,便产生了一个暑假速成算法的计划,可能对于像我这种算法竞赛小白而言,几乎很难,但我仍然还是想尝试一下,毕竟,梦想还是要有的,万一实现了呢?~( ̄▽ ̄~)~

在这里插入图片描述


为什么选择码蹄集作为刷题软件?

码蹄集,是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的,其依托全国各大名校计算机系和清华大学出版社等单位的强大资源,旨在为计算机学习爱好者提供全面和权威的计算机习题。
在这里插入图片描述


目录

1. MT2276 数的自我

(1)题目描述
提瓦特大陆上有一个贫穷的占星术士小码哥,出于占星术的要求,他时常要解决一些困难的数学问题。这天,上天给了他一个启示:有一类称作 Self一Numbers的数。对于每一个正整数n,我们定义d(n)为n加上它每一位数字的和。例如,d(75)= 75+7+5=87。给定任意正整数n作为一个起点,都能构造出一个无限递增的序列: n,d(n), d(d(n)), d(d(d(n))),…例如,如果你从33开始,下一个数是33+3+3=39,再下一个为39+3+9=51,再再下一个为51+5+1=57,因此你所产生的序列就像这样:33,39,51,57,69,84,96,111,114,120,123,129,141,…数字n被称作d(n)的发生器。在上面的这个序列中,33是39的发生器,39是51的发生器,51是57的发生器等等。有一些数有超过一个发生器,如101的发生器可以是91和100。一个没有发生器的数被称作Self 一Number。如前13个 Self - Number为1,3,5,7,9,20,31,42,53,64,75,86,97。我们将第i个Self -Number表示为a[i],所以a[1]= 1,a[2]= 3,a[3]=5…

现在小码哥需要找到一个[1,N]的区间内所有的Self - Number,请你帮帮他。

格式

输入格式:
第一行输入以空格隔开的两个整数Ⅳ和K,第二行输入K个以空格隔开的整数$1,82,s3 . . . Sk 。
.
输出格式:
第一行你需要输出一个数,这个数表示在闭区间[1,N]中Self - Number的数量。
第二行必须包含以空格分隔的K个数,表示a[s1] …a[sk],这里保证所有的a[s1] …a[sg.]都小于N。(例如,如果N=100,s:可以为1-13,但不能为14,因为a[14]=108 > 100)。

样例1

输入:
100 10
1 2 3 4 5 6 7 11 12 13
.
输出:
13
1 3 5 7 9 20 31 75 86 97

备注:

其中:1<N ≤107,1<K ≤5000。

(2)参考代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int cnt,n,k;
int ans[1000010];
bool flag[10000010];
int next(int num){int ans=0;ans+=num;while(num!=0){ans+=num%10;num/=10;}return ans;
}
int main(){memset(flag,true,sizeof(flag));scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)if(flag[i]){ans[++cnt]=i;int now=next(i);while(now<=n&&flag[now]) {flag[now]=false;now=next(now);}}printf("%d\n",cnt);int t=0;for(int i=1;i<=k;i++){scanf("%d",&t);printf("%d ",ans[t]);}
}

2. MT2277 分数个数

(1)题目描述

定义简分数为,分母d >分子n,且不可以再约分。

如果我们把d≤6的所有简分数以从小到大的顺序排列,则有:
1/6,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,5/6,可以看到这个集合中包含的分数有11个。给定d,求这个最简分数集合中包含有多少个分数?

格式

输入格式: 一个整数d。
.
输出格式: 输出一个整数表示包含的分数的个数。

样例1

输入: 6
.
输出: 11

备注:

提示:2<d≤105。

(2)参考代码

#include<bits/stdc++.h>
using namespace std;int main()
{long long n,i,k,ans,t,sum;scanf("%lld",&n);sum=0;for(k=2;k<=n;k++){ans=k;t=k;for(i=2;i*i<=t;i++){if(t%i==0){ans-=ans/i;while(t%i==0) t/=i;}}if(t!=1) ans -= ans/t;sum+=ans;}printf("%lld\n",sum);return 0; return 0;
}

3. MT2278 欧拉函数

(1)题目描述
给出给定正整数n,求f(n),此处f(n)定义为小于n的所有与n互素的数的个数。


格式

输入格式: 一个整数n 。
.
输出格式: 输出一行一个整数表示答案。

样例1

输入格式: 4
.
输出格式: 2

备注:

其中:2≤n ≤1e9。

(2)参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxa = 1e10 + 10;
LL euler_deall(LL n)
{LL res = n;for (LL i = 2; i * i <= n; i++){if (n % i == 0){res = res / i * (i - 1);for (; n % i == 0; n /= i);}}if (n != 1)res = res / n * (n - 1);return res;
}
int main()
{LL n;scanf("%lld", &n);printf("%lld\n", euler_deall(n));
}

4. MT2279 欧拉函数2

(1)题目描述

给出给定正整数n,求1f(i),此处f(n)定义为小于等于n并且与n互质的数的个数。(此处认为1与1互质)


格式

输入格式: 一个正整数n。
.
输出格式: 输出一行一个整数表示答案。

样例1:

输入: 4
.
输出:6

备注:

其中: 1≤n ≤ 1e6

(2)参考代码

def main():n = int(input())primes = [] # 存质数values = [1] * (n + 1) # 存欧拉函数的值values[0] = 0 # 0的欧拉函数值为0st = [True for _ in range(n + 1)] # 存每个数是否是质数for i in range(2, n + 1):  # 对于每个大于2的自然数if st[i]:  # 如果是质数,加入质数列表,质数的欧拉函数值为i-1primes.append(i)values[i] = i - 1for p in primes:if p > n / i: breakst[p * i] = False  # p*i不是质数,设置为False# 如果i % p != 0 p不是i的质因数,则eulor(p*i) = p * eulor(i) * (p-1) / p = (p-1)* eulor(i)values[p * i] = (p - 1) * values[i]if i % p == 0:# 如果i % p = 0, p是i的质因数,则eulor(p*i) = p * eulor(i)values[p * i] = p * values[i]breakprint(sum(values))if __name__ == '__main__':main();

5. MT2280 数字游戏

(1)题目描述
在这里插入图片描述


格式

输入格式: 输入只有一行两个整数,分别代表宗教数m 和房间数n。
.
输出格式: 输出一行一个整数代表答案。

样例1

输入格式: 2 3
.
输出格式: 6

备注:

其中: 1≤m ≤le8,1 ≤n ≤1e10

(2)参考代码

#include<bits/stdc++.h> 
/*
思路:不越狱的状态好计算所以:越狱数=总的状态数-不越狱的状态数
其中 总的状态数为:m^n不越狱的状态数: m*(m-1)^(n-1) :只有第一个可以选择m个宗教,其他的只能选和前一个不同的宗教所以是m-1种情况
这里计算用了快速幂的方法。
*/
using namespace std;
long long p=1007;
long long qpow(long long x, long long y){if(y==0)return 1;if(y%2==1){return qpow(x, y - 1) * x % p;}else{long long t = qpow(x, y/2) % p;return t*t % p;}
}
int main( )
{long long m,n;cin>>m>>n;long long ans = qpow(m,n)-(m*qpow(m-1,n-1)%p);cout<<(ans+p)%p<<endl;//注意需要+p之后再取 %p,防止有负数return 0;
}

结语

感谢大家一直以来的不断支持与鼓励,码题集题库中的进阶塔350题正在逐步更新,之后会逐步跟进星耀,王者的题,尽请期待!!!
同时,也希望这些题能帮助到大家,一起进步,祝愿每一个算法道路上的“苦行僧”们,都能够历经磨难,终成正果,既然选择了这条路,走到了这里,中途放弃,岂不是太过可惜?

另附中国计算机学会的杰出会员、常务理事轩哥博士的B站视频讲解链接https://space.bilibili.com/518554541/?spm_id_from=333.999.0.0,供大家更好的进行学习与刷题~( ̄▽ ̄~)~

愿你的结局,配得上你一路的颠沛流离。

这篇关于算法竞赛入门【码蹄集进阶塔335题】(MT2276-2280)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/327800

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题: