acwing蓝桥杯 - 数学知识【下】

小黄同学LL 2024-01-11 原文

欧拉函数

在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目，记作φ(n). φ(1)=1

1、分解质因子，求出质因子p

2、将p带入，套公式

为了代码方便，套第三个公式

#include <iostream>

using namespace std;


int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            //欧拉计算公式，等价于res*=(1-1/p),防止小数导致精度丢失
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}


int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        cout << phi(x) << endl;
    }

    return 0;
}

补充：

若a与m互质，则有

快速幂

大佬算法讲解：

举个栗子：

如上例所示：

利用a取平方操作，构建k的2的次幂和

#include <iostream>
using namespace std;
typedef long long LL;

int quick_pow(int a, int k, int p)//二进制优化
{
    int res = 1 % p;//表示取模总值
    while (k) {
        if (k & 1) res = (LL)res * a % p;//相乘等价于a的次幂相加,使得k=2的次幂和
        k >>= 1;
        a = (LL)a * a % p;//使k进制进一位
    }
    return res;
}

int n;

int main()
{
    cin >> n;
    while (n--) {
        int a, k, p;
        cin >> a >> k >> p;
        cout << quick_pow(a, k, p) << endl;
    }
    return 0;
}

求组合数 I

如上公式：从a个苹果里选b个的选法=包含红苹果的选法+不包含红苹果的选法；

包含：除去必选的红苹果，就是在a-1个苹果里选b-1个的选法

不包含：直接丢掉红苹果，在a-1个苹果里选b个

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2010, mod = 1e9 + 7;

int c[N][N];

void init()//预处理
{
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) c[i][j] = 1;//i==0时j必等于0,初始化c[0][0]
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;//套公式
}

int main()
{
    int n;
    init();

    scanf("%d", &n);
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);

        printf("%d\n", c[a][b]);
    }
    return 0;
}

博弈论

Nim游戏

结论：

先手必败状态：a1 ^ a2 ^ a3 ^ ... ^an = 0
先手必胜状态：a1 ^ a2 ^ a3 ^ ... ^an ≠ 0

1、若处于先手必败状态，则无论怎么操作，之后都会变成先手必胜状态

2、若处于先手必胜状态，则必有一次操作能使得状态变为先手必败状态

记忆：

当所有值相同，如剩下2 2两堆，先手无论怎么操作，后手只需要做镜像操作即可胜利；记忆特殊情况，当所有值相同，则a1 ^ a2 ^ a3 ^ ... ^an = 0，则先手必败

#include <iostream>
#include <cstdio>
using namespace std;

/*
先手必胜状态：先手操作完，可以走到某一个必败状态
先手必败状态：先手操作完，走不到任何一个必败状态
先手必败状态：a1 ^ a2 ^ a3 ^ ... ^an = 0
先手必胜状态：a1 ^ a2 ^ a3 ^ ... ^an ≠ 0
*/

int main(){
    int n;
    scanf("%d", &n);
    int res = 0;
    for(int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    if(res == 0) puts("No");
    else puts("Yes");
}

蓝桥 acwing 先手 xff xff0c 蓝桥杯算法 c++数据结构学习

有关acwing蓝桥杯 - 数学知识【下】的更多相关文章

ruby - 我怎样才能更好地了解/了解更多关于 Ruby 的知识？ - 2
按照目前的情况，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visitthehelpcenter指导。关闭9年前。我最近开始学习Ruby，这是我的第一门编程语言。我对语法感到满意，并且我已经完成了许多只教授相同基础知识的教程。我已经写了一些小程序(包括我自己的数组排序方法，在有人告诉我谷歌“冒泡排序”之前我认为它非常聪明)，但我觉得我需要尝试更大更难的东西来理解更多关于Ruby.关于如何执行此操作的任何想法？
ruby - 我可以在 Ruby 中动态调用数学运算符吗？ - 2
ruby中有这样的东西吗？send(+,1,2)我想让这段代码看起来不那么冗余ifop=="+"returnarg1+arg2elsifop=="-"returnarg1-arg2elsifop=="*"returnarg1*arg2elsifop=="/"returnarg1/arg2 最佳答案是的，只需像这样使用send(或者更好的是public_send):arg1.public_send(op,arg2)这是可行的，因为Ruby中的大多数运算符(包括+、-、*、/、andmore)只需调用方法。所以1+2与1.+(2)相同
蓝桥杯备赛（二） - 2
目录前言：一、ASC分析代码实现二、卡片分析代码实现三、直线分析代码实现四、货物摆放分析代码实现小结：前言：在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。一、ASC 已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy
ruby |设计数学？ - 2
情况:我正在编写一个程序来求解素数。我需要解决4x^2+y^2=n的问题，其中n是一个已知变量。是的，必须是Ruby。我愿意在这个项目上花费大量时间。我最好自己编写方程式的求解算法，并将其作为该项目的一部分。我真正喜欢的是:如果任何人都可以向我提供指南、网站的链接，或者关于与求解代数方程特别相关的形式算法的构造的歧义消除，或者向我提供似乎你是读者它会帮助我完成任务。请不要建议我使用其他语言。如果您在回答之前接受我真的非常想这样做，我将不胜感激。该项目没有范围或时间限制，也不以营利为目的。这是为了我自己的教育。注意:我并不直接反对为Ruby实现和使用现存的数学库/模块/其他东西，但我更喜
ruby - 我在哪里可以找到 Ruby 中的数学密集型应用程序 - 2
我发现许多Rails应用程序主要针对企业、社交网络类型的Web应用程序。我看到有人将Ruby与一些出色的OOPS语言(如Java和C#)进行了比较，但我确实发现很难获得一些数学密集型应用程序。非常感谢任何知识渊博的输入(指向示例程序的链接等)，其中轻松显示了语言的用法，就像快速启动或显示该语言如何用于各种数学问题一样。最佳答案不幸的是，Ruby并没有在数学和科学计算领域涉足太多。目前，有一个名为SciRuby的pre-alpha库它试图为Ruby带来更多面向数学的功能。他们正试图构建一个NumPy/SciPy等价物。SciRub
蓝桥杯C/C++VIP试题每日一练之报时助手 - 2
?作者主页：静Yu?简介：CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家，前端知识交流社区创建者?社区地址：前端知识交流社区?博主的个人博客：静Yu的个人博客?博主的个人笔记本：前端面试题个人笔记本只记录前端领域的面试题目，项目总结，面试技巧等等。接下来会更新蓝桥杯官方系统基础练习的VIP试题，依然包括解题思路，源代码等等。问题描述：给定当前的时间，请用英文的读法将它读出来。时间用时h和分m表示，在英文的读法中，读一个时间的方法是：　　如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“threeo’clock”。　　如果m不为0，则将时读出来，然后将分读出来，如5
ruby - Ruby基础知识 - 2
Asitcurrentlystands,thisquestionisnotagoodfitforourQ&Aformat.Weexpectanswerstobesupportedbyfacts,references,orexpertise,butthisquestionwilllikelysolicitdebate,arguments,polling,orextendeddiscussion.Ifyoufeelthatthisquestioncanbeimprovedandpossiblyreopened,visitthehelpcenter提供指导。已关闭8年。什么是学习ruby语言
十四届蓝桥青少组模拟赛Python-20221108 - 2
十四届蓝桥青少组模拟赛Python-20221108T1.二进制位数十进制整数2在十进制中是1位数，在二进制中对应10，是2位数。十进制整数22在十进制中是2位数，在二进制中对应10110，是5位数。请问十进制整数2022在二进制中是几位数？print(len(bin(2022))-2)#运行结果：11T2.晨跑小蓝每周六、周日都晨跑，每月的1、11、21、31日也晨跑。其它时间不晨跑。已知2022年1月1日是周六，请问小蓝整个2022年晨跑多少天？#样例代码1ls=[0,31,28,31,30,31,30,31,31,30,31,30,31]ans=0k=6foriinrange(1,13)
蓝桥杯 stm32 MCP4017 - 2
本文代码使用HAL库。文章目录前言一、MCP4017的重要特性二、MCP4017计算RBW阻值三、MCP4017地址四、MCP4017读写函数五、CubeMX创建工程（利用ADC测量MCP4017电压）、对应代码：总结前言一、MCP4017的重要特性蓝桥杯板子上的是MCP4017T-104ELT，如图1。MCP4017是一个可编程电阻，通过写入的数值可以改变电阻的大小。重点在于6引脚（W），5引脚（B&#
[蓝桥杯单片机]学习笔记——串口通信的基本原理与应用 - 2
目录一、原理部分1、什么是串行通信（1）并行通信与串行通信（2）串行通信的制式（3）串行通信的主要方式 2、配置串口（1）SCON和PCON：串行口1的控制寄存器（2）SBUF：串行口数据缓冲寄存器（3）AUXR：辅助寄存器编辑（4）ES、PS：与串行口1中断相关的寄存器（5）波特率设置 3、串口框架编写二、程序案例一、原理部分1、什么是串行通信（1）并行通信与串行通信微控制器与外部设备的数据通信，根据连线结构和传送方式的不同，可以分为两种：并行通信和串行通信。并行通信：数据的各位同时发送与接收，每个数据位使用一条导线，这种方式传输快，但是需要多条导线进行信号传输。串行通信：数据一位一

acwing蓝桥杯 - 数学知识【下】

欧拉函数

快速幂

求组合数 I

博弈论

Nim游戏

有关acwing蓝桥杯 - 数学知识【下】的更多相关文章

随机推荐