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

这篇具有很好参考价值的文章主要介绍了算法竞赛入门【码蹄集进阶塔335题】(MT2281-2285)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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



前言

mt2179 码题集,云曦算法,算法,c++,数据结构,码蹄集

为什么突然想学算法了?

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

mt2179 码题集,云曦算法,算法,c++,数据结构,码蹄集


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

码蹄集,是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的,其依托全国各大名校计算机系和清华大学出版社等单位的强大资源,旨在为计算机学习爱好者提供全面和权威的计算机习题。
mt2179 码题集,云曦算法,算法,c++,数据结构,码蹄集


目录

1. MT2281 另一种模

(1)题目描述
给定正整数n,k和n个正整数 c1, C2,…" ,Cn。如果对于任意正整数x,可以通过mod c的值推出a mod k的值则输出Yes否则输出No

格式

输入格式: 第一行n, k,第二行为数列c
.
输出格式: 输出Yes或者No

样例1

输入:
4 5
2 3 5 12
.
输出格式: Yes

备注:

n, k,c[i] ≤1e6 。

(2)参考代码

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int maxn = 100010;
int n, k, num = 1;
int prime[maxn];
int main() {
    cin >> n >> k;
    vector<int> c(n+1);
    map<int, int> M;
    for(int i = 1; i <= n; i++)
        cin >> c[i];
    prime[1] = 2;  
    int hhh = k;
    for(int i = 2; i <= hhh; i++) {
        if(k < i) break;
        if(k % i == 0) {
            int ttt = true;
            for(int j = 1; j <= num; j++)
              if(i % prime[j] == 0 && i != prime[j]) {
                  ttt = false;
                  break;
              }
            if(!ttt) continue;
            prime[++num] = i;
            int temp = i;
            while(k % temp == 0) temp *= i;
            temp /= i;
            k /= temp;
            bool t = false;
            for(int j = 1; j <= n; j++) {
                if(c[j] % temp == 0) {
                    t = true;
                    break;
                }
            }
            if(!t) {
                printf("No");
                return 0;
            }
        }
    }
    printf("Yes");
    return 0;
}

2. MT2282 小码哥的认可

(1)题目描述
定义一个正整数α,它有p(az)个约数;如果这个数满足对于任意的i,属于0<i<a,有p(z)> p(i),那么它就受到小码哥的认可;比如840就是被小码哥认可的数。

现在给你一个N,求小于等于N的最大的小码哥的认可数。

格式

输入格式: 一个数N(1≤N≤2,000,000,000) 。
.
输出格式: 表示小于等于N的最大的小码哥的认可数。

样例1

输入: 1000
.
输出: 840

备注:

提示(1<N ≤ 2,000,000,000) .

(2)参考代码


'''
一个数值的约束个数等于其分解质因数之后,每个质因子上 "次幂加1" 的乘积,2*10……9以内的数值约数个数1600个左右,因此按照
约数个数给数值分类,显然每一类中的最小值才可能是候选的解,因此可以对2~1600的数做因数分解,每个值代表月数个数每个因子对
应一个质因子次幂,显然这个因子序列应该要非降序,第1个因子数值 = 质因子2的次幂+1,第2个因子数值 = 质因子3次幂+1 ......
DFS递归分解 2~1600,就可以得到每一类中的最小值,再用这些候选答案组成一个序列,进行升序排序,然后逐个验证是否满足要求,
最终实际的出来的候选序列长度只有70, 在这70个数值中二分找答案即可
也可以打表
'''
# -*- coding: utf-8 -*-
import time
from typing import List, Tuple
from collections import deque, Counter
from queue import PriorityQueue
import math
from functools import lru_cache
#from sortedcontainers import SortedDict, SortedSet
import random
import copy
import sys
sys.setrecursionlimit(99999999)
# 质数表
P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
all_vals = {1 : 1}
# 将数值分解成非降序的约数乘积形式,每个约束大于等于2
def devide(arr:List, val, orig):
    if val == 1:
        ans = 1
        n = len(arr)
        for i in range(len(arr)):
            ans *= P[i] ** (arr[n-1-i]-1)
        if ans <= 2000000000:
            if orig not in all_vals:
                all_vals[orig] = ans
            else:
                all_vals[orig] = min(ans, all_vals[orig])
        return
    min_v = arr[-1] if len(arr) > 0 else -1
    for d in range(2, val+1):
        if val % d == 0 and d >= min_v:
            arr.append(d)
            devide(arr, val // d, orig)
            arr.pop(-1)
def main():
    # # 枚举约数个数,2*10^9以内的数值约数最多1600个左右,这里上界设置成1700
    for i in range(2, 1701):
        devide([], i, i)
    #print(all_vals)
    vals = [(v, k) for k, v in all_vals.items()]
    vals.sort()
    mx = -1
    buf = []
    for a, b in vals:
        if b > mx:
            buf.append(a)
        mx = max(mx, b)

    N = int(input())
    ans = None
    l, r = 0, len(buf)-1
    while l <= r:
        mid = (l + r) >> 1
        if buf[mid] <= N:
            ans = buf[mid]; l = mid + 1
        else:
            r = mid - 1
    print(ans)
if __name__ == '__main__':
    main();

3. MT2283 整数的逆

(1)题目描述
定义p = 1000000007,给定一个正整数n,求一个小于p的正整数,使得n * Z在模p意义下为1,即存在正整数k,使得n * 优 = k* p+1


格式

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

样例1

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

备注:

其中:1≤n ≤1,000,000,000 。

(2)参考代码

MOD = 10**9 + 7
def pow_mod(a, k, p):
    ans = 1
    pow_val = a % p
    while k != 0:
        if k & 1 != 0:
            ans = (ans * pow_val) % p
        pow_val = (pow_val ** 2) % p
        k >>= 1
    return ans
def rev_meta(b, p):
    return pow_mod(b, p-2, p)
def main():
    n = int(input())
    print(rev_meta(n, MOD))
if __name__ == '__main__':
    main();

4. MT2284 行列式

(1)题目描述
给出矩阵,求其行列式。


格式

输入格式:
第一行输入T表示数据组数。
对于每组数据,第一行输入n表示边长。接下来n行,每行输入n个整数,代表矩阵的元素。
.
输出格式: 对于每组数据,输出矩阵的行列式,答案请对0z1f1f1f1f取模。

样例1:

输入
3
3
1 -2 -1
0 3 2
3 1 -1
3
0 3 2
1 -2 -1
3 1 -1
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
.
输出
522133271
8
0

(2)参考代码

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long  lld;
lld a[15][15];
int sign;
lld N, MOD = 0x1f1f1f1f;
void solved()
{
    lld ans = 1;
    for (int i = 0; i < N; i++) //当前行
    {
        for (int j = i + 1; j < N; j++) 
        {
            int x = i, y = j;
            while (a[y][i]) //利用gcd的方法,不停地进行辗转相除
            {
                lld t = a[x][i] / a[y][i];
                for (int k = i; k < N; k++)
                    a[x][k] = (a[x][k] - a[y][k] * t) % MOD;
                swap(x, y);
            }
            if (x != i) //奇数次交换,则D=-D'整行交换
            {
                for (int k = 0; k < N; k++)
                    swap(a[i][k], a[x][k]);
                sign ^= 1;
            }
        }
        if (a[i][i] == 0) //斜对角中有一个0,则结果为0
        {
            cout << 0 << endl;
            return;
        }
        else
            ans = ans * a[i][i] % MOD;
    }
    if (sign != 0)
        ans *= -1;
    if (ans < 0)
        ans += MOD;
    printf("%lld\n", ans);
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        sign = 0;
        scanf("%lld", &N);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                scanf("%lld", &a[i][j]);
        solved();
    }
    return 0;
}

5. MT2285 矩阵乘法

(1)题目描述


格式

输入格式:

.
输出格式:

样例1

输入格式:
4 3 4
1 2 3
4 -5 6
7 8 9
-3 2 1
4 5 6 7
8 6 9 7
0 0 1 0
.
输出格式:
20 17 27 21
-24 -10 -15 -7
92 83 123 105
4 -3 1 -7

备注:

其中: 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,供大家更好的进行学习与刷题~( ̄▽ ̄~)~

愿你的结局,配得上你一路的颠沛流离。文章来源地址https://www.toymoban.com/news/detail-724876.html

到了这里,关于算法竞赛入门【码蹄集进阶塔335题】(MT2281-2285)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法竞赛入门【码蹄集进阶塔335题】(MT2271-2275)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月07日
    浏览(31)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2201-2225)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月08日
    浏览(31)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2286-2290)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月06日
    浏览(31)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2076-2100)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2023年04月19日
    浏览(47)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2226-2250)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月11日
    浏览(35)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2291-2295)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月06日
    浏览(31)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2151-2175)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月02日
    浏览(50)
  • 算法竞赛入门【码蹄集新手村600题】(MT1020-1040)

    码蹄集网站地址:https://www.matiji.net/exam/ojquestionlist (1)题目 输入一个实数,第一次按实型输出;第二次保留2位小数输出;第三次保留3位小数但最小列宽8列输出,空格分隔。 格式 样例1 (2)参考代码 (1)题目 输出3.1415926、12345678.123456789的小数、指数形式。 格式 样例1 (

    2024年02月16日
    浏览(42)
  • 算法竞赛入门【码蹄集新手村600题】(MT1280-1300)C语言

    码蹄集网站地址:https://www.matiji.net/exam/ojquestionlist (1)题目 输入正整数N(1500),首先计算其逆序数M(比如12逆序后是21)。然后输出N的M次方的最后3位数。 格式 样例1 (2)参考代码 (1)题目 一个自然数,如果每一位数的位数次幂之和等于该自然数,则称之为Disarium数。 比如

    2024年02月07日
    浏览(41)
  • 供水管线 码蹄集

    首先,题目要求我们去掉一些管道,使得总的管道管理费用最小。在去掉部分管道的情况下,城市之间不再形成一个回路,即城市之间构成了一棵树。因此,我们需要找到一棵生成树,使得所有管道管理费用之和最小。 接下来,我们需要选择合适的算法来寻找最小生成树。常

    2024年02月06日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包