HENAU冬令营 数学专题

2023-10-08 05:20
文章标签 数学 专题 冬令营 henau

本文主要是介绍HENAU冬令营 数学专题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A - A^B Mod C
给出3个正整数A B C，求A^B Mod C。
例如，3 5 8，3^5 Mod 8 = 3。
Input
3个正整数A B C，中间用空格分隔。(1 <= A,B,C <= 10^9)
Output
输出计算结果
Sample Input
3 5 8
Sample Output
3
快速幂详解

#include<bits/stdc++.h>
using namespace std;typedef long long ll;int qpow(ll a,ll b,ll p)
{ll ans=1;while(b){if(b&1)ans=ans*a%p;b>>=1;a=a*a%p;}return ans;
}
ll a,b,p;
int main()
{cin>>a>>b>>p;cout<<qpow(a,b,p)<<endl;return 0;
}

B - 逆元
阿克克希是求婚总动员的队长，他通过自己的双手，成就了无数年轻人的梦，但他却留下了悲伤的泪水。
求婚是非常费力的，他手上有 P-1 个求婚请求，这 ii 个人的编号为 [1,P-1]
面对第 i 个人他的求婚麻烦值为：i在模 P意义下的逆元。
他现在想知道总的麻烦值。
tips:如果有任意一个编号 i在模 P 意义下不存在逆元，请输出 AKCniubi
输入格式
一行一个数 P 表示求婚请求总数
输出格式
一行一个数表示总麻烦值
若有数存在无逆元的情况，输出 AKCniubi
数据范围
对于 30% 的数据，P<=1000000
对于 50% 的数据，P<=10000000
对于 100% 的数据，P<=2^{31}
Sample Input
3
Sample Output
3
在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
ll is_primes(ll x)
{for(int i=2;i<=x/i;i++){if(x%i==0)return 0;}return 1;
}int main()
{ll p,ans;cin>>p;	if(is_primes(p))ans=(p-1)*(p)/2;else {cout<<"AKCniubi"<<endl;return 0;}if(p==2)ans=1;cout<<ans<<endl;return 0;
}

C - 判决素数个数
输入两个整数X和Y，输出两者->>之间<<-的素数个数（包括X和Y）。
Input
两个整数X和Y（1 <= X,Y <= 105）。
Output
输出一个整数，表示X，Y之间的素数个数（包括X和Y）。
Sample Input
1 100
Sample Output
25
知识点：线性筛
注意就是x不一定比y小

#include<bits/stdc++.h>
using namespace std;const int N=1e5+10;
int primes[N],vis[N];
int cnt=0;void get_primes(int n)
{for(int i=2;i<=n;i++){if(vis[i]==0)primes[cnt++]=i;for(int j=0;primes[j]<=n/i;j++){vis[primes[j]*i]=1;if(i%primes[j]==0)break;}}
}
int main()
{int a,b;get_primes(100000);cin>>a>>b;int ans=0;if(a>b)swap(a,b);for(int i=0;i<cnt;i++){if(primes[i]>=a&&primes[i]<=b)	ans++;}cout<<ans;return 0;
}

D - 矩阵乘法
计算两个矩阵的乘法。n×m 阶的矩阵 A乘以 m×k 阶的矩阵 B 得到的矩阵 C 是 n×k 阶的.
输入格式
第一行为 n, m, k，表示 A矩阵是 n行 m 列，B矩阵是 m 行 kk列，n, m, k均小于 100；
然后先后输入 A和 B 两个矩阵，A矩阵 n行 m列，B矩阵 m 行 k 列，矩阵中每个元素的绝对值不会大于 1000。
输出格式
输出矩阵 C，一共 n行，每行 k 个整数，整数之间以一个空格分开。
Sample Input
3 2 3
1 1
1 1
1 1
1 1 1
1 1 1
Sample Output
2 2 2
2 2 2
2 2 2

#include<bits/stdc++.h>
using namespace std;const int N=110;int a[N][N],b[N][N],c[N][N];
int main()
{int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>a[i][j];}for(int i=1;i<=m;i++)for(int j=1;j<=k;j++){cin>>b[i][j];}for(int i=1;i<=n;i++)for(int j=1;j<=k;j++){for(int l=1;l<=m;l++){c[i][j]+=a[i][l]*b[l][j];}}for(int i=1;i<=n;i++)for(int j=1;j<=k;j++){cout<<c[i][j]<<" ";if(j==k)cout<<endl;}	return 0;
}

E - Bash游戏
有一堆石子共有N个。A B两个人轮流拿，A先拿。每次最少拿1颗，最多拿K颗，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N和K，问最后谁能赢得比赛。
例如N = 3，K = 2。无论A如何拿，B都可以拿到最后1颗石子。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000) 第2 - T + 1行：每行2个数N，K。中间用空格分隔。（1 <= N,K <= 10^9)
Output
共T行，如果A获胜输出A，如果B获胜输出B。
Sample Input
4
3 2
4 2
7 3
8 3
Sample Output
B
A
A
B
规律题

#include<bits/stdc++.h>
using namespace std;int main()
{int t;cin>>t;while(t--){int a,b;cin>>a>>b;if(a%(b+1))cout<<"A"<<endl;else cout<<"B"<<endl;}return 0;
}

F - 取石子游戏
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
Input
输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。
Output
输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。
Sample Input
2 1
8 4
4 7
Sample Output
0
1
0

威佐夫博弈的必败条件
abs(a,b)∗(1+√5)/2=min(a,b)

#include<bits/stdc++.h>
using namespace std;int main()
{int a,b;while(cin>>a>>b){int temp=abs(a-b);int ans=temp*(1+sqrt(5.0))/2.0;if(ans==min(a,b))cout<<"0"<<endl;else cout<<"1"<<endl; }return 0;
}

G - Matches Game
这是一个简单的游戏。在这个游戏中，有几堆火柴和两名玩家。这两个玩家轮流进行。在每一轮中，玩家可以选择一堆并从堆中取出任意数量的火柴（当然，取出的火柴数量不能为零，也不能大于所选堆中的火柴数量）。如果一名玩家取完火柴后，没有剩下火柴，该玩家就是赢家。假设这两个玩家都会作出最优决策。你的工作是判断先手玩家能否赢得比赛。
Input
输入由几行组成，每行中都有一个测试用例。 在一行的开头，有一个整数M（1<=M<=20），它是火柴堆的数量。然后是M个不大于10000000的正整数。这些M个整数表示每堆中的火柴数。
Output
对于每个测试用例，如果第一个玩家获胜，在一行中输出“Yes”，否则输出“No”。
Sample Input
2 45 45
3 3 6 9
Sample Output
No
Yes

#include<bits/stdc++.h>
using namespace std;int main()
{int n;while(cin>>n){int ans=0;while(n--){int x;cin>>x;ans^=x;}if(ans==0)cout<<"No"<<endl;else cout<<"Yes"<<endl;}return 0;
}

H - 互质数的个数（一）
这里我们定义φ(n) 表示所有小于等于 n 与 n 互质数的个数。
例如φ(10)=4，因为我们可以在1∼10 中找到1,3,7,9 与 10互质。
输入格式
第一行输入一个整数 t，表示测试数据组数。
接下来 t 行，每行有一个整数 n。
输出格式
对于每组测试数据输出 φ(n) 。
数据范围
1≤t≤100,1≤n≤1e10。
Sample Input
3
2
10
100
Sample Output
1
4
40

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
int main()
{int n;cin>>n;while(n--){ll a;cin>>a;ll res=a;for(int i=2;i<=a/i;i++){if(a%i==0){res=res/i*(i-1);while(a%i==0)a/=i;}}if(a>1)res=res/a*(a-1);cout<<res<<endl;}return 0;
}

I - Sumdiv
题目描述
有两个自然数a和b(a,b≤50000000)
求a的b次方的所有约数之和模9901
输入格式
一行，包含由空格分隔的两个自然数a和b
输出格式
一行，a的b次方的约数和模9901
样例输入
2 3
样例输出
15
样例解释
8的约数是1,2,4,8， 它们的总和是15
15模9901是15

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
const int N=10000;
const int mod=9901;int n,m;
int dis[N],vis[N];ll qpow(ll a,ll b)
{ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}ll f(ll a,ll b)
{if(b==0)return 1;else if(b%2)return (f(a,b/2)*(1+qpow(a,b/2+1)))%mod;else return (f(a,b/2-1)*(1+qpow(a,b/2+1))+qpow(a,b/2))%mod;}int main()
{cin>>n>>m;unordered_map<int,int>primes;for(int i=2;i<=n/i;i++){while(n%i==0){n/=i;primes[i]++;}}if(n>1)primes[n]++;ll res=1;for(auto p:primes){ll a=p.first,b=p.second;res=(res*f(a,b*m)%mod)%mod;}cout<<res<<endl;return 0;
}

J - The Lottery
题目描述
给出n , m，和m个数a[1]⋯a[m]。
求1⋯n中不被a[1]⋯a[m]中任意一个整除的数的个数。
10⩽n<2^{31}231,1⩽m⩽15
输入格式
每组数据以n,m为第一行。
第二行m个数，表示a[i]。
输入文件以EOF结尾。
输出格式
每组数据一行一个数字表示答案。
样例输入
10 2
2 3
20 2
2 4
样例输出
3
10

#include<bits/stdc++.h>
using namespace std;typedef long long ll;ll gcd(ll a,ll b)
{return b?gcd(b,a%b):a;
}ll lcm(ll a,ll b)
{return a/gcd(a,b)*b;
}int a[20];int main()
{int n,m;while(cin>>n>>m){for(int i=0;i<m;i++)cin>>a[i];int k=pow(2,m),ans=n,res;for(int i=1;i<k;i++){ll l=1;res=0;for(int j=0;j<m;j++){if(i&(1<<j)){l=lcm(l,a[j]);res++;}}if(res&1)ans-=n/l;else ans+=n/l;}cout<<ans<<endl;	}return 0;
}

K - 组合数问题
题目

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
const int N=2010;ll t,k,n,m,f[N][N],s[N][N];int main()
{cin>>t>>k;for(int i=0;i<=2000;i++){f[i][i]=1;f[i][0]=1;}for(int i=1;i<=2000;i++)for(int j=1;j<i;j++){f[i][j]=(f[i-1][j]+f[i-1][j-1])%k;}for(int i=1;i<=2000;i++)for(int j=1;j<=2000;j++){s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1];if(f[i][j]==0&&j<=i)s[i][j]++;}while(t--){cin>>n>>m;cout<<s[n][m]<<endl;	}	return 0;
}

L - 同余方程
求关于 xx 的同余方程 ax≡1(modb) 的最小正整数解。
输入格式
输入只有一行，包含两个正整数 a,b，用一个空格隔开。
输出格式
输出只有一行，包含一个正整数X0，即最小正整数解。输入数据保证一定有解。
数据范围
对于 40% 的数据2≤b≤1,000；
对于 60% 的数据2≤b≤50,000,000；
对于 100% 的数据2≤a,b≤2,000,000,000。
Sample Input
3 10
Sample Output
7

#include<bits/stdc++.h>
using namespace std;typedef long long ll;ll x,y;
void exgcd(ll a,ll b)
{if(b==0){x=1;y=0;return ;}exgcd(b,a%b);ll tx=x;x=y;y=tx-a/b*y;
}int main()
{ll a,b;cin>>a>>b;exgcd(a,b);x=(x%b+b)%b;cout<<x;	return 0;
}

这篇关于HENAU冬令营 数学专题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/162975。

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

原文链接： https://tecdat.cn/?p=37628 6月16日，小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞，这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示，公司准备量产，并计划今年四季度开启预售小鹏汇天分体式飞行汽车，探索分体式飞行汽车城际通勤。阅读原文，获取专题报告合集全文，解锁文末271份飞行汽车相关行业研究报告。 据悉，业内人士对飞行汽车行业
阅读更多...
uva 10014 Simple calculations（数学推导）

uva 10014 Simple calculations（数学推导）

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导，第二次没有继续下去。 代码： #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf
阅读更多...
uva 10025 The ? 1 ? 2 ? ... ? n = k problem（数学）

uva 10025 The ? 1 ? 2 ? ... ? n = k problem（数学）

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k，? 处可以填 + 也可以填 - ，问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明，令 S（n） = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n，搜出当 S（n） >=
阅读更多...
uva 11044 Searching for Nessy（小学数学）

uva 11044 Searching for Nessy（小学数学）

题意是给出一个n*m的格子，求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码： #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col
阅读更多...
【生成模型系列（初级）】嵌入（Embedding）方程——自然语言处理的数学灵魂【通俗理解】

【生成模型系列（初级）】嵌入（Embedding）方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入（Embedding）方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节：嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”，它将文本中的单词或短语转换成计算机能够理解的数学形式，即向量。 正如翻译机将一种语言
阅读更多...
数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2
阅读更多...
音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础：WAV专题（6）——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道，通过FFprobe命令可以打印WAV音频文件每个packet（也称为数据包或多媒体包）的信息，这些信息包含该packet的pts、dts： 打印出来的“pts”实际是AVPacket结构体中的成员变量pts，是以AVStream->time_base为单位的显
阅读更多...
专题二_滑动窗口_算法专题详细总结

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口，引入： 滑动窗口，本质：就是同向双指针； 1.⻓度最⼩的⼦数组（medium） 1.解析：给我们一个数组nums，要我们找出最小子数组的和==target，首先想到的就是暴力解法 1）暴力： 2）优化，滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串（medium） 1）仍然是暴力解法： 2）优化： 进窗口：hash[s[rig
阅读更多...
CSP-J基础之数学基础 初等数论 一篇搞懂(一)

CSP-J基础之数学基础 初等数论 一篇搞懂(一)

文章目录 前言声明初等数论是什么初等数论历史1. **古代时期**2. **中世纪时期**3. **文艺复兴与近代**4. **现代时期** 整数的整除性约数什么样的整数除什么样的整数才能得到整数？条件：举例说明：一般化： 判断两个数能否被整除 因数与倍数质数与复合数使用开根号法判定质数哥德巴赫猜想最大公因数与辗转相除法计算最大公因数的常用方法：举几个例子：例子 1: 计算 12 和 18
阅读更多...
2024年AMC10美国数学竞赛倒计时两个月：吃透1250道真题和知识点（持续）

2024年AMC10美国数学竞赛倒计时两个月：吃透1250道真题和知识点（持续）

根据通知，2024年AMC10美国数学竞赛的报名还有两周，正式比赛还有两个月就要开始了。计划参赛的孩子们要记好时间，认真备考，最后冲刺再提高成绩。 那么如何备考2024年AMC10美国数学竞赛呢？做真题，吃透真题和背后的知识点是备考AMC8、AMC10有效的方法之一。通过做真题，可以帮助孩子找到真实竞赛的感觉，而且更加贴近比赛的内容，可以通过真题查漏补缺，更有针对性的补齐知识的短板。
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2