• 马蹄集matji oj赛（第十二次）

    目录

    元素共鸣

    欧拉函数

    欧拉函数2

    小码哥的喜欢数

    整数的逆

    数的自我

    阶乘的质因子

    分数个数

    质数率

    数字游戏

    元素共鸣


    难度：黄金
    0时间限制：1秒
    巴占用内存：128M
    遥远的大陆上存在着元素共鸣的机制。
    建立一个一维坐标系，其中只有素数对应的点的坐标存在着元素力，而相距为飞的两个元素力之
    间能形成元素共鸣。现在，需要求出范围内所有能元素共鸣的点对，并将他们以第一个点的坐
    标大小为关键字排序后输出（小的在前）。
    格式
    输入格式：一行两个整数几，k。
    输出格式：所有小于等于的素数对。每对素数奴对输出一行，中间用单个空格隔开。
    若没有找到任何素数对，输出empty。

    1. //
    2. // Created by abner on 2023/10/11.
    3. //
    4. #include 
    5. using namespace std;
    6. const int N =1e4+ 7;
    7. bool judge[N];
    8. int prime[N],cnt;
    9. int getPrimes(int n) {
    10.     for (int i = 2; i <= n; i++) {
    11.         if (!judge[i])
    12.             prime[cnt++] = i;
    13.         for (int j = 0; prime[j] * i <= n; j++) {
    14.             judge[prime[j] * i] = true;
    15.             if (i % prime[j] == 0)
    16.                 break;
    17.         }
    18.     }
    19.     return cnt;
    20. }
    21. int main(){
    22.             int n,k;
    23.             bool flag = false;
    24.             cin >>n >>k;
    25.             getPrimes(n);
    26.             for (int i=0;i
    27.                 int n1 = prime[i], n2 = n1 + k;
    28.                 if (n2 <= n && !judge[n2]) {
    29.                     cout << n1 << " " << n2 << endl;
    30.                     flag = true;
    31.                 }
    32.             }
    33.                 if (!flag)
    34.                     cout <<"empty";
    35.                 return 0;
    36.             }

    欧拉函数


    难度:黄金时间限制: 1秒四占用内存:128M
    给出给定正整数 n，求 f(n)，此处 f(n)定为小于n 的所有与n 素的数的个数
    格式
    一个整数n。输入格式:
    输出格式:输出一行一个整数表示答案
    样例1
    输入:4
    输出:2

    1. //
    2. // Created by abner on 2023/10/11.
    3. //
    4. #include 
    5. using namespace std;
    6. int n;
    7. int euler_phi(int n){
    8.     int ans = n;
    9.     for (int i=2;i*i<=n;i++)
    10.         if(n%i==0) {
    11.             ans = ans / i * (i - 1);
    12.             while (n % i == 0) n /= i;
    13.         }
    14.             if (n > 1) ans=ans /n *(n -1);
    15.             return ans;
    16.         }
    17.     int main(){
    18.         cin >>n;
    19.         cout <<euler_phi(n);
    20.         return 0;
    21.     }

    欧拉函数2


    难度: 钻石时间限制: 1秒四占用内存: 128M
    给出给定正整数 n，求”f()，此处 f(n)定义为小于等于 n 并且与 n 质的数的个数(此处认为 1与1互质)
    格式
    输入格式:一个正整数n。
    输出格式:输出一行一个整数表示答案
    样例1
    输入:4
    输出:6

    1. //
    2. // Created by abner on 2023/10/11.
    3. //
    4. #include 
    5. using namespace std;
    6. #define int long long
    7. const int N = 1e6 +7;
    8. bool judge [N];
    9. int prime [N],cnt,phi[N],n,sum;
    10. void getPhi(int n){
    11.     phi[1]=1;
    12.     for (int i=2;i<=n;i++) {
    13.         if (!judge[i]) {
    14.             prime[cnt++] = i;
    15.             phi[i] = i - 1;
    16.         }
    17.         for (int j = 0; prime[j] * i <= n; j++) {
    18.             judge[prime[j] * i] = true;
    19.             if (i % prime[j] == 0) {
    20.                 phi[prime[j] * i] = prime[j] * phi[i];
    21.                 break;
    22.             } else
    23.                 phi[prime[j] * i]=(prime[j] - 1) * phi[i];
    24.         }
    25.     }
    26. }
    27.             signed main() {
    28.                 cin >> n;
    29.                 getPhi(n);
    30.                 for (int i = 1; i <= n; i++)
    31.                     sum += phi[i];
    32.                 cout << sum << endl;
    33.                 return 0;
    34.             }

    小码哥的喜欢数


    难度: 钻石
    时间限制: 1秒四占用内存:128M
    小码哥不喜欢以下情况的数:
    1.是7的倍数(包括7);
    2.数字的某一位是7，这种数字的倍数，小码哥也不喜欢。
    小码哥会给你 t个数，如果这个数是他喜欢的数，那么告诉他下一个他喜欢的数是多少(即大于这个数的下一个他喜欢的数)。如果这个数他不喜欢，那你要告诉他。
    格式
    输入格式:第1行，一个正整数T表示小码哥给你的数接下来T行，每行1个整数2，表示这一次小码哥给的数
    输出格式:输出共T行，每行一个整数。如果这个数是他喜欢的数，那么告诉他下一个他喜欢的数是多少(即大于这个数的下一个他喜欢的数) ;如果这个数他不喜欢，那你要输出 -1 ;

    1. //
    2. // Created by abner on 2023/10/11.
    3. //
    4. #include 
    5. using namespace std;
    6. const int N = 1e7 +7;
    7. int T,x,ans [N],nxt [N],cnt;
    8. bool judge[N]={1};
    9. bool check(int x) {
    10.     while (x) {
    11.         if (x % 10 == 7)
    12.             return true;
    13.         x /= 10;
    14.     }
    15.     return false;
    16. }
    17.     int getNums(int n){
    18.         int curr = 1;
    19.         for (int i=2;i<=n;i++){
    20.             if (!judge[i]) {
    21.                 bool flag = check(i);
    22.                 if (!flag) {
    23.                     ans[cnt++] = i;
    24.                     nxt[curr] = i;
    25.                     curr = i;
    26.                 } else {
    27.                     for (int j = i; j <= n; j += i)
    28.                         judge[j] = true;
    29.                 }
    30.             }
    31.         }
    32.         return cnt;
    33.     }
    34.  
    35. int main(){
    36.     getNums(N);
    37.     cin >>T;
    38.     while (T--){
    39.         cin >>x;
    40.         if (judge[x])
    41.             cout <<-1 <
    42.         else{
    43.             cout <
    44.     }
    45. }
    46. return 0;
    47. }

    整数的逆


    难度:黄金时间限制: 1秒四占用内存:128M
    定义p=1000000007，给定一个正整数n，求一个小于p 的正整数，使得 n * 在p 意义下为1，即存在正整数 k，使得n*e=k*p+1。
    格式
    一个正整数n。输入格式:
    输出格式:输出一行一个整数  表示答案
    样例1
    输入: 500000004
    输出:2

    1. //
    2. // Created by abner on 2023/10/11.
    3. //
    4. #include 
    5. using namespace std;
    6. #define int long long
    7. int n,mod = 1e9 +7;
    8. long long binpow(long long a,long long b,long long m){
    9.     a%=m;
    10.     long long res = 1;
    11.     while (b > 0){
    12.     if (b & 1)
    13.     res = res * a % m;
    14.     a=a * a % m;
    15.     b>>=1;
    16. }
    17. return res;
    18. }
    19. signed main(){
    20.     cin >>n;
    21.     cout <<binpow(n,mod -2,mod);
    22.     return 0;
    23. }

    数的自我


    难度: 钻石时间限制: 0.75秒四占用内存:128M
    提瓦特大陆上有一个贫穷的占星术士小码哥，出于占星术的要求，他时常要解决一些困难的数学问题。这天，上天给了他一个启示: 有一类称作 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 表示为ai，所以a1=1,a2] = 3,a 3 =5...
    现在小码哥需要找到一个1N 的区间内所有的 Self-Number ，请你帮帮他。

    1. //
    2. // Created by abner on 2023/10/11.
    3. //
    4.  
    5. #include 
    6. using namespace std;
    7. const int N=1e7 +7;
    8. int ans[N],cnt,n,k;
    9. bool judge[N];
    10. int cal(int x) {
    11.     int ans = x;
    12.     while (x) {
    13.         ans += x % 10;
    14.         x /= 10;
    15.     }
    16.     return ans;
    17. }
    18. int getNums(int n) {
    19.     for (int i = 1, temp; i <= n; i++) {
    20.         temp = cal(i);
    21.         if (temp <= n)
    22.             judge[temp] = true;
    23.         if (!judge[i])
    24.             ans[cnt++] = i;
    25.     }
    26.     return cnt;
    27. }
    28.     int main(){
    29.         cin >>n >>k;
    30.         cout <<getNums(n)<
    31.         int x;
    32.         while (k--) {
    33.             cin >> x;
    34.             cout << ans[x - 1] << " ";
    35.         }
    36.             return 0;
    37.         }

    阶乘的质因子


    难度:钻石时间限制: 1秒占用内存: 128 M
    小码哥有一天想把20!表示出来，但是小码哥意识到这个数字算出来将非常大，于是你给小码哥出主意，用算术基本定理的形式表示，于是这个任务理所应当的被小码哥推给了你，正好你想干点简单的事来换换脑子，就接受了。你要把 N! 按照算术基本定理的形式表示。
    基本算数定理:一个数一定可以用一下形式表示:a = p(1]1] * p(2)c2l*..... *p(jl ;
    pli 为质数数组， cl 为每一个质数的幂的次数对于不同的 a 来说，有不同的 p 和 c 数组。
    格式
    输入格式:输入一个整数N
    输出格式: N!分解质因数后的结果，共若干行，每行两个数 p,c,表示含有 p项。按照

    1. //
    2. // Created by abner on 2023/10/11.
    3. //
    4. #include 
    5. using namespace std;
    6. #define int long long
    7. const int N = 1e6 +7;
    8. bool judge [N];
    9. int prime[N],cnt,n;
    10. int getPrimes(int n) {
    11.     for (int i = 2; i <= n; i++) {
    12.         if (!judge[i])
    13.             prime[cnt++] = i;
    14.         for (int j = 0; prime[j] * i <= n; j++) {
    15.             judge[prime[j] * i] = true;
    16.             if (i % prime[j] == 0)
    17.                 break;
    18.         }
    19.     }
    20.     return cnt;
    21. }
    22.         signed main(){
    23.             cin >> n;
    24.             getPrimes(n);
    25.             for (int i=0;i
    26.                 int ans =0,r=prime[i];
    27.                 while (r <= n){
    28.                     ans +=n /r;
    29.                     r *= prime[i];
    30.                     }
    31.                     if (ans)
    32.                         cout <" "<
    33.                 }
    34.                 return 0;
    35.             }

    分数个数


    难度: 钻石时间限制: 1.5秒四占用内存:128M
    定义简分数为，分母d >分子n ，且不可以再约分
    如果我们把 d< 6 的所有简分数以从小到大的顺序排列，则有:1/6,1/5,1/4,1/3,1/2,2/5,2/3,3/5,3/4,4/5,5/6 ，可以看到这个集合中包含的分数有11个。给定 d ，求这个最简分数集合中包含有多少个分数?
    格式
    输入格式:一个整数 d.
    输出格式:输出一个整数表示包含的分数的个数

    1. //
    2. // Created by abner on 2023/10/11.
    3. //
    4. #include 
    5. using namespace std;
    6. #define int long long
    7. const int N = 1e6 + 7;
    8. bool judge [N];
    9. int prime [N],cnt,phi[N],n,sum;
    10. void getPhi(int n){
    11.     phi[1]=1;
    12.     for (int i=2;i<=n;i++){
    13.         if (!judge[i]){
    14.             prime[cnt++] = i;
    15.         phi[i] = i-1;
    16.     }
    17.     for (int j=0;prime[j]* i<=n;j++) {
    18.         judge[prime[j] * i] = true;
    19.         if (i % prime[j] == 0) {
    20.             phi[prime[j] * i] = prime[j] * phi[i];
    21.             break;
    22.         } else
    23.             phi[prime[j] * i] = (prime[j] - 1) * phi[i];
    24.     }
    25.     }
    26. }
    27. signed main(){
    28.     cin >>n;
    29.     getPhi(n);
    30.     for (int i = 2;i <= n;i++)
    31.     sum += phi[i];
    32.     cout <
    33.     return 0;
    34. }

    质数率


    难度:黄金时间限制: 1秒四占用内存:256M
    请你求出 1,n 范围内质数占比率
    格式
    输入格式:只有一行，一个整数 n ，含义如题目描述。
    输出格式:输出[1,n 范围内质数占比，保留3 位小数
    样例1
    输入:10
    输出:8.409

    1. //
    2. // Created by abner on 2023/10/11.
    3. //
    4. #include 
    5. using namespace std;
    6. const int N = 1e8 +7;
    7. bool judge[N];
    8. int prime[N],cnt,n;
    9. int getPrimes(int n) {
    10.     for (int i = 2; i <= n; i++) {
    11.         if (!judge[i])
    12.             prime[cnt++] = i;
    13.         for (int j = 0; prime[j] * i <= n; j++) {
    14.             judge[prime[j] * i] = true;
    15.             if (i % prime[j] == 0)
    16.                 break;
    17.         }
    18.     }
    19.     return cnt;
    20. }
    21. int main(){
    22.     scanf("%d",&n);
    23.     getPrimes(n);
    24.     printf("%.3lf\n",(double)cnt/n);
    25.     return 0;
    26. }

    数字游戏


    难度:黄金时间限制: 1秒四占用内存:128 M
    小码哥和小码妹正在玩一个小游戏，小码哥先展示一个正整数 n，如果小码妹可以写出 k个正整数21···2k 满足]I-(+ 1)=n，则她可以得到  分。小码妹的数学并不好，所以请你写一个程序帮忙计算她最多可以得到多少分。
    格式
    输入格式:一行，一个正整数 n e2,1x 108
    输出格式:一行，一个正整数
    样例1
    输入:12

    1. //
    2. // Created by abner on 2023/10/11.
    3. //
    4. #include 
    5. using namespace std;
    6. int n,ans;
    7. int main(){
    8.     cin >>n;
    9.     for (int i = 2;i*i<=n;i++)
    10.     while(n%i== 0) {
    11.         ans++;
    12.         n /= i;
    13.     }
    14.     if(n>1)
    15.     ans++;
    16.     cout <
    17.     return 0;
    18. }

  • 相关阅读:
    大模型 RAG 是什么?
    自动化测试之路 —— Appium安装教程
    backward问题记录
    迁移学习
    【面试题】Vue2动态添加路由 router.addRoute()
    Java abstract 关键字(keyword)
    用python开发一个炸金花小游戏
    监控系统--Zabbix
    linux共享文件问题
    如何在MATLAB中创建和操作矩阵？
  • 原文地址：https://blog.csdn.net/m0_62574889/article/details/133767427