马蹄集 oj赛(双周赛第十七次)
目录
疗养院的福利
难度:白银时限制:4秒占用内存: 64 M
小码哥是一家疗养院的院长，疗养院有 N(1< N< 1000) 个人，现在疗养院有个福利政策年龄最大的 n(1 < n<N) 个人免费居住，有很多人都想报名参加。小码哥对报名参加的统计年龄[ii,i2,i3,4,...n ，其中 ?为最先报名的人， 为最后报名的人，如果有多人年龄相同的人，取相同年龄中最先报名的n人(数组左边为最先报名的人)，你能帮小码哥找到符合福利政策的n个人吗?
格式
第一行一个整数N(1 ?N1000) 表示报名的人数;输入格式:第二行以空格分割，长度为 N(1N1000) 的数组表示参加福利政策的人的年龄集合;
第三行一个整数 n(1<nN) 示能能参加的福利最大年的人数
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1007;
struct PERSON{
int age;
int ID;}
p[MAX];
int N,n;
bool cmp(PERSON a,PERSON b) {
if (a.age == b.age)
return a.ID < b.ID;
return a.age > b.age;
}
int main(){
cin >>N;
for (int i=1;i <= N;i++){
cin >>p[i].age;
p[i].ID = i;
}
sort(p +1,p +N + 1,cmp);
cin >>n;
for (int i=1;i <= n;i++)
cout <<p[i].ID <<" ";
return 0;}
密码判断器
难度:白银时间限制: 1秒四占用内存:64M
小码哥在是一位密码领域的初学者，有一天他的老师给他了一串密码，要他判断这个密码是否是强密码，老师和他说强密码就是需要同时达到以下要求:
1.密码长度大于6。
2.密码中同时包括了大小写字母和数字。
3.并且数字和数字之间不能相连。
现在有一个长度为 N(1 N<100000)的密码串，你能帮他判断这个密码串是不是强密码吗?
格式
输入格式:一行一个长度为 N(1 N 100000) 的字符串表示为密码串
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >>s;
int len =s.length();
if(len<=6) {
cout << "False";
return 0;
}
bool hasUpper = false,hasLower = false,hasDigit = false;
for (int i=0;i<len;i++){
if (isupper(s[i]))
hasUpper = true;
else if (islower(s[i]))
hasLower = true;
else if (isdigit(s[i]))
hasDigit = true;
}
if (!(hasUpper && hasLower && hasDigit)){
cout <<"False";
return 0;
}
for (int i=1;i<len;i++) {
if (isdigit(s[i]) && isdigit(s[i - 1])) {
cout << "False";
return 0;
}
}
cout<<"True";
return 0;}
小码哥锻炼
难度:白银时间限制: 1秒四占用内存:256 M小码哥想到了一个很好玩的锻炼方式，他在花园里挖了一个坑，坑能够容纳的沙子的总的重量是n 千克，他通过往坑里面运沙子的方式把坑填满，沙子装在特定的桶里面，有四种桶，每种装满分别可以装13千克、7千克、3千克、1千克的沙子。小码哥是个有强迫症的人，他每次运沙子都必须把桶装满，而且必须在最后一次恰好填满这个坑对于小码哥来说，每一种桶都是一样，他不挑剔重量，但是他想装沙子的次数尽可能的少请你帮助小码哥计算成最少的运沙子的次数
格式
输入格式: n(1n 100000)，坑能够容纳的沙子的总重量
输出格式:最少的运沙子的次数
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
int n,ans;
int main(){
cin >>n;
while (n >=13)
ans++,n-=13;
while (n >= 7)
ans++,n-=7;
while (n>=3)
ans++,n-=3;
while (n >= 1)
ans++,n-=1;
cout <<ans;
return 0;
}
小码哥和假期堵车
难度:白银四占用内存:256M时间限制: 1秒
小码哥在通关一个游戏，他知道需要 t 分钟才能通关这个游戏。并且小码哥希望快点通关
但是，在接下来的 n 天里，小码哥的朋友不幸被堵在了假期回家的高速上，朋友总是在车堵的开不动的时候，在社交软件上找小码哥聊天。第 i天，小码哥需要花 ; 分钟的时间来朋友聊天。这天剩余的时间只有大于等于一个小时，小码哥才可以玩游戏(假定该游戏可以中途存档，下次可以接着玩不用重新开始)。
请您帮助小码哥确定他能够通关的最早日期。答案保证不超过 n。
备注:一天有1440分钟。
格式
第一行包含两个整数n和t(1< n< 100，1<t 10)- 天数和通关所需的输入格式:
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 107;
int n,t,temp;
int main(){
cin>>n>>t;
for (int i=1;i <=n;i++){
cin >>temp;
if(1440-temp<60)
continue;
t-=1440-temp;
if(t<=0){
cout <<i;
return 0;
}
}
}
小码哥的数字游戏
四占用内存:256M时间限制: 1秒
难度:白银
小码哥在玩一个很有趣的数字游戏。给定一个 NXM 规模的矩阵，矩阵中全部都是整数。小码哥想要找到一个最小的子矩阵，使得这个子矩阵中包含了所有的小于等于T的数字 (小于等于T的数字最少有一个)。
请你帮助小码哥解决这个问题。编写一个程序，输入一个 NXM 的矩阵，输出这个最小矩阵的行数和列数。
格式
输入格式:第一行包含两个整数 N 和 M，表示矩阵的行数和列数。(1 < N,M50);第二行表示数字T (1<T<1000 )接下来N行，每行有 个数字，表示矩阵 NXM中的每个数字这些数字的范围是0到10000，包括0和10000，而且他们中小于等于T的最少有-
公
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
int N,M,T,num[57][57];
//记录左上角和右下角两个点的坐标x和y
int max_row =-1,max_col =-1,min_row = 60,min_col = 60;
int main() {
cin >> N >> M >> T;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++) {
cin >> num[i][j];
if (num[i][j] > T)
continue;
min_row = min(min_row, i);
min_col = min(min_col, j);
max_row = max(max_row, i);
max_col = max(max_col, j);
}
cout << (max_row - min_row + 1) << endl;
cout << (max_col - min_col + 1);
return 0;
}
小码哥和密码学
黄金难度:
时间限制: 1秒占用内存:256 M
小码对密码学很感兴趣，他自己发明了一种加密算法:
(1)字母a使用数字0表示，字母b使用数字1表示..，字母使用数字25表示，字母ba使用数字26表示，字母bb使用数字27表示..，字母bz使用数字51表示。字母ca使用数字52表示..，依次类推(2)和上面的完全相反，数字0使用字母a表示，数字1使用字母b表示..，数字25使用字母z表示,数字26使用字母ba表示，数字27使用字母bb表示..，数字51使用字母bz表示，数字52使用字母ca表示...，依次类推。
(3)对于连续的字母或者数字，按照上面的规律将字母转为数字，数字转为字母。(4)连续的数字最长不超过各语言长整型能够表示的大小，字母转换来的数字也不超过各语言长整型能够表示的大小。
(5)特别强调的是，连续的数字不会以0开头，连续的字母不会以a开头。请编写一个程序，帮他完成这个加密过程
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
string s,temp,ans;
int StoI(string s) {//字符串“123"转化成int类型123
int len = s.length(), temp = 0;
for (int i = 0; i < len; i++)
temp = temp * 10 + s[i] - '0';
return temp;
}
string ItoS(int n) {//int类型123转化成字符串“123”
string temp = "";
if (n == 0)
temp = "0";
while (n) {
temp = (char) (n % 10 + '0') + temp;
n = n / 10;
}
return temp;
}
string convert(string s){
string ss ="";
if(isdigit(s[0])){//数字转化成字母
int temp = StoI(s);
if (temp ==0)
ss = "a";
while (temp){
ss = (char)(temp % 26 +'a') + ss;
temp = temp / 26;
}
}else{//字母转化成数字
int temp = 0;
for (int i=0;i<s.length();i++)
temp = temp * 26 +s[i]-'a';
ss = ItoS(temp);
}
return ss;
}
int main() {
cin >> s;
int len = s.length();
s = "#" + s;
for (int i = 1; i <= len; i++) {
if (isdigit(s[i - 1]) && isdigit(s[i]) ||
isalpha(s[i - 1]) && isalpha(s[i])) {
temp = temp + s[i];
} else {
if (temp != "")
ans += convert(temp);
temp = s[i];
}
}
ans += convert(temp);
cout << ans;
return 0;
}
小码哥的浇花选择
难度:白银
时间限制: 1秒占用内存: 256 M
小码哥养了两种花，为了让花更加健康，小码哥制定了复杂的浇花策略，他给两种花分别赋予了-个浇花的系数 ?和 y 。现在小码哥有一桶工升的水，开始的时候，小码哥会给第一个花浇水，浇水的量是系数 ?和桶里面剩余的水的差的绝对值，过了一个小时，小码哥会给第二个花浇水，浇水的量是系数 y 和桶里面剩余的水的差的绝对值，如此循环。两种花间隔排布。当小码哥已经完成了某一次的浇花，正准备开始下一次的浇花时(正准备的意思是还没有开始)，如果它发现桶里面剩余的水已经不够浇花时(不够的意思是，桶里面剩余的水，严格的小于浇花需要的水)，他会停止浇花(停止浇花的意思是，还没有浇的这一次就不浇了，整个浇花过程也完全停止了) 。
请你帮助小码哥计算出来他给两种花分别浇了多少的水注意:不需要考虑绝对值为0的情况。
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
int x,y,L;
int ansx,ansy;
int main(){
cin >>x >>y >>L;
int need , flag =1;
while (true) {
if (flag == 1) {
need = abs(x - L);
if (L < need)
break;
ansx += need, L -= need;
flag = 2;
} else {
need = abs(y - L);
if (L < need)
break;
ansy += need, L -= need;
flag = 1;
}
}
cout <<ansx <<" "<<ansy;
return 0;
}
星辰大海
难度:钻石时间限制: 4秒四占用内存:256M
公元 3099 年，地球人终于实现了星空梦。在大量先驱的探索下，星空旅游终于实现了。小码哥抓住机会，马上开了一家星空旅游公司。小码哥的星舰每排有 p 个座位，一共有 g 排，所以，座椅形成了一个 p x g 的网格(不考虑过道)。小码哥对每次星舰的出行，都出售 k张票。为了安全，座位必须遵守以下规则:座位被占用时，座位的前后左右四个方向的座位必须是空的。同时为了满足旅客的独特体验，小码哥则是对每一趟尾舰的座位采取不同的安排，如果这一趟的某个座位是占用的，而另一趟的座位是空的，则这两趟星舰座位安排是不同的。现在需要从这些座位中选出 k个合法的座位，请问有多少种选择方法?由于这个数字可能非常大，我们只求它对337077 取模的结果。
格式
输入格式:第一行包含一个整数 T，表示指定测试用例的数量每个测试用例由包含三个整数 p， ? 和的一行组成
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
const int MOD = 337077;
int m,n,k,num,mp[90][90];
void dfs(int a,int counts){
if (counts ==k){
num++;
return;
}
for (int i=a + 1;i <= n * m;i++){
int x = ceil((float)i / m);
int y = i%m;
if (y ==0)
y = m;
if(!mp[x-1][y] && !mp[x+1][y] && !mp[x][y-1] && !mp[x][y]){
mp[x][y]=1;
counts++;
dfs(i,counts);
counts--;
mp[x][y] = 0;
}}}
int main(){
int t;
cin >>t;
while (t--){
cin >>m >>n >>k;
memset(mp,0,sizeof(mp));
num =0;
dfs(0,0);
cout <<num % MOD <<endl;
}
return 0;
}
王国傀儡师
难度:黄金时间限制: 10秒四占用内存:256M
在一个奇幻的王国中，存在着一个名叫小码哥的魔法师。小码哥手下收藏着 n 个傀儡，他靠着手下的傀儡演出赖以生存。因此，傀儡的魅力度与他的生存息息相关。他为每个傀儡都进行了编号，即从 1 到 n。对于编号为 k 的，假设存在有序整数对 (a,b,c) 满足 abc = k那么编号为 k的傀儡的魅力度定义为满足上式的所有有序整数对的个数之和。现在，他想知道他手下所有的傀儡的魅力度之和是多少，只有这样，他才能知道下周是否有饭吃。请将结果除以3333求余。
格式
输入格式:输入包含一个整数 n，表示小码哥手下收藏着n个儡
输出格式:输出一行一个整数表示小码哥手下所有的傀儡的魅力度之和除以 3333 所得的余数
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 3333;
int n,ans,tmp;
signed main(){
cin >> n;
//处理a<b<c,即三个数各不相同
for (int a = 1;a * a * a < n;a++)
for (int b = a + 1;a * b * b<n;b++){
tmp = n/ (a * b)-b;
if (tmp > 0)
ans += 6 * tmp;
ans %= MOD;
}
//只有两个数相同且1小2大
for (int a = 1;a*a*a < n;a++){
tmp = sqrt(n / (a))-a;
if (tmp > 0)
ans +=3 * tmp;
ans %= MOD;
}
//只有两个数相同且2小1大
for (int a = 1;a*a*a < n;a++){
tmp = n / (a*a)-a;
if (tmp > 0)
ans += 3 * tmp;
ans %= MOD;
}
//处理a=b=c,即三个数都相同
for (int a = 1;a*a*a <= n;a++)
ans++;
cout <<ans % MOD;
return 0;
}
寻找聪明学者
难度:白银时间限制: 1秒兴占用内存:256M
在小码哥的世界里，有一群学者们集结在一起。每个学者都有自己的聪明水平，这可以用一个整数来表示。他们站成一排，小码哥需要找到其中三个相邻的聪明水平递增的学者(即长度至少为 3的相邻递增子序列)。如果存在长度至少为 3 的递增子序列，返回 True: 否则，返回 False
你的任务是帮助小码哥编写一个函数，判断是否存在这样的子序列。
格式
输入格式:第一行一个整数 n(1 n <100000) 表示有 n 个学者站一排。第二行一个长度为n的整数数组，用空格隔开，每个元素 ni(1n<10000)表示学者们的聪明水平，聪明水平是整数。
输出格式:一行一个字符串，如果存在长度至少为 3 的递增子序列，返回 True;否则，返回False。
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
const int N=1e5 + 7;
int n,nums [N];
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> nums[i];
if (n >= 3)
for (int i = 0; i < n - 2; i++)
if (nums[i] < nums[i + 1] && nums[i + 1] < nums[i + 2]) {
cout << "True";
return 0;
}
cout << "False";
return 0;
}
凡家物语
难度: 钻石时间限制: 1秒世占用内存:256M
凡家物语是 Minecraft 游戏的一个模组，添加了大量的村民社交与互动，包括但不限于跟所有村民交谈、送礼甚至是结婚生子，旨在创造属于自己的故事。每个村民都有自己的名字，且有独立的好感度，任何互动都将对好感度产生影响。
小码哥酷爱这个模组，在游戏里他不会放过任何一个村民，每每遇见都会交流互动一番，并将每一位村民的名字和好感度记录在册。不幸的是他开的和平难度，没有村民死亡，随着时间的推移，其数量越来越多，而且有的村民还和别人同名，这使得名册越来越臃肿，所以他急需你帮他维护这个名册。
他需要你实现 4 种操作:
1.如果遇到新的村民，记录其名字 si及好感度 ai;
2.修改一个家族所有人的好感度，即给定名字前缀 pi 的所有人的好感度变化 di;3.查询名字为 si 的村民们的声望值的和(因为会有重名的);
4.查询一个家族所有人的好感度总和，即名字前缀为 pi 的好感度的和。
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 +7;
int n,ans;
struct TRIE {
int nex[N][26], cnt, exist[N],
sum[N];//exist:表示这个名字有多少个，sum表示这个名字的声望和
void insert(string s, int d) {//插入字符串
int p = 0, len = s.length();
for (int i = 0; i < len; i++) {
int c = s[i] - 'a';
if (!nex[p][c])
nex[p][c] = ++cnt;//如果没有，就添加结点
p = nex[p][c];
}
exist[p]++;//exist[]表示一共插入了多少个进来
sum[p] += d;
}
int find(string s) {//查找字符串
int p = 0, len = s.length();
for (int i = 0; i < len; i++) {
int c = s[i] - 'a';
if (!nex[p][c])
return 0;
p = nex[p][c];
}
return p;
}
void modify(int x, int d) {
if (exist[x])
sum[x] += d * exist[x];
for (int i = 0; i < 26; i++) {
if (!nex[x][i])
continue;
modify(nex[x][i], d);
}
}
void search(int x) {
if (exist[x])
ans += sum[x];
for (int i = 25; i >= 0; i--) {
if (!nex[x][i])
continue;
search(nex[x][i]);
}
}
}trie;
int main() {
cin >> n;
int op, d;
string s;
while (n--) {
cin >> op;
if (op == 1) {//遇到新的村民
cin >> s >> d;
trie.insert(s, d);
} else if (op == 2) {//修改一个家族的声望
cin >> s >> d;
int x = trie.find(s);
if (x)
trie.modify(x, d);
} else if (op == 3) {//查询一个名字的声望和
cin >> s;
int x = trie.find(s);
cout << trie.sum[x] << endl;
} else {//查询一个家族的声望和
cin >> s;
ans = 0;
int x = trie.find(s);
if (x)
trie.search(x);
cout << ans << endl;
}
}
return 0;
}
防火墙
时间限制: 1秒四占用内存:256M
难度:黄金
服务器是计算机的一种，在网络中为其它客户机提供计算或者应用服务，每天的访问量非常大，其中包括正常访问，也有非法攻击。
小码哥在一家互联网公司担任网络安全工程师，负责过滤掉非法攻击，确保服务器的正常运行。这家公司的服务器有一个很长的数字串标识，每个客户端的请求也有一个很长的数字串标识，若两个数字串循环同构(由一个字符串通过循环移位得到的另一个字符串，两个字符串具有相同的字符组成和相同的长度，例如abcd'通过循环移位可以得到bcda’cda’和dabc’,这些字符串就是循环同构)，则请求通过，否则将被视为非法攻击
此外，如果是循环同构，小码哥还要求必须输出该字符串的最小表示。
注:字符串S的最小表示指的是与 S 环同构的所有字符串中字典序最小的字符串。
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
int func(string a) {
int n = a.length();
int k = 0, i = 0, j = 1;
while (k < n && i < n && j < n) {
if (a[(i + k) % n] == a[(j + k) % n]) {
k++;
} else {
a[(i + k) % n] > a[(j + k) % n] ? i = i + k + 1 : j = j + k +1;
if (i == j)
i++;
k = 0;
}
}
return min(i, j);
}
int main(){
string a,b,a1,b1;
cin >>a >>b;
int pos = func(a),pos2 = func(b);
a1 = a.substr(pos) + a.substr(0,pos);
b1 = b.substr(pos2)+b.substr(0,pos2);
if (a1 == b1)
cout <<"Yes"<<endl <<a1;
else
cout <<"No";
return 0;
}
组合游戏
星耀难度:
时间限制: 10秒占用内存: 256 M
受到数学中的组合的启发，小码哥发明了一种好玩的组合游戏。有编号为1到n的n个数字，编号为i的数字的值是 ai，其中 ai 可正可负。小码哥需要从这些数字里选取k个组合，要求:
(1)每个组合的数字的个数不少于 L 且不多于 R。
(2)选择组合的时候，要求选择编号连续的数字(不支持循环连续，即类似于编号n-1，编号n,
编号1不构成一个连续)。(3)组合之间两两不相同。 (两个组合相同，当且仅当两个组合选择的数字的编号完全相同，比如组合1选择了编号为2、3、4的数字，组合2也选择了编号为2、3、4的数字，则它们相同)对于选出k个组合，有很多种的选法。但是小码哥想知道所有的选法里，能够让这k个组合的所有的数字的和最大，这个最大值是多少。
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n,k,L,R,sum[N],F[N][20];
long long ans;
void ST_create(){
for (int i=1;i<=n;i++)
F[i][0]=i;
int k = log2(n);
for (int j=1;j<=k;j++)
for(int i=1;i<=n-(1<<j) + 1;i++) {
int x = F[i][j - 1], y = F[i + (1 << (j - 1))][j - 1];
F[i][j] = sum[x] > sum[y] ? x : y;
}}
int ST_query(int l,int r) {
int k = log2(r - l + 1);
int x = F[l][k], y = F[r - (1 << k) + 1][k];
return sum[x] > sum[y] ? x : y;
}
struct NODE {
int start, end_l, end_r, max_ID;
NODE(int s, int e_l, int e_r) {
start = s, end_l = e_l, end_r = e_r;
max_ID = ST_query(end_l, end_r);
}
bool operator<(const NODE &b) const {
return sum[max_ID] - sum[start - 1] < sum[b.max_ID] - sum[b.start - 1];
}
};
priority_queue<NODE> q;
int main() {
cin >> n >> k >> L >> R;
for (int i = 1; i <= n; i++) {
cin >> sum[i];
sum[i] += sum[i - 1];
}
ST_create();
for (int i = 1; i <= n; i++)//初始化优先队列
if (i + L - 1 <= n)
q.push(NODE(i, i + L - 1, min(i + R - 1, n)));
while (k--) {
NODE tmp = q.top();
q.pop();
int s = tmp.start, e_l = tmp.end_l, e_r = tmp.end_r, m_ID = tmp.max_ID;
ans += sum[m_ID] - sum[s - 1];
if (m_ID != e_l)
q.push(NODE(s, e_l, m_ID - 1));
if (m_ID != e_r)
q.push(NODE(s, m_ID + 1, e_r));
}
cout << ans;
return 0;
}
多重堡垒
难度:黄金时间限制: 3秒四占用内存:256M
小码哥最近迷上了游戏:多重堡垒，他想计算这个游戏的复杂程度，请你帮助他。这个游戏可以抽象为一颗满二叉树(满二又树首先的一颗二又树，然后它的每一层的节点数都达到了最大值)。
这个满二叉树有 n 个结点，每个节点都有一个正整数权值 vi。游戏的复杂程度，等于每一个节点的复杂程度的和。每一个节点的复杂程度的计算方式为: 对于以该节点为根的子树，树上的每一个节点(包括根节点)的权值 vi，乘以该节点到当前的根节点的唯一简单路径所包含的边数(一个节点到本身的边数是0)，等于该节点的加权权值。则子树上所有的节点的加权权值，取最大值，作为该子树的根节点的复杂程度。
请你求出游戏的复杂程度
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 +7;
int n,a[N],ans;
int getMax(int index,int edge) {
if (index > n)
return 0;
int rootValue = edge * a[index];
int leftValue = getMax(index * 2, edge + 1);
int rightValue = getMax(index * 2 + 1, edge + 1);
return max(max(rightValue, leftValue), rootValue);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
ans += max(getMax(i * 2, 1), getMax(i * 2 + 1, 1));
cout << ans;
return 0;
}
循环
难度:星耀时间限制:1秒四占用内存:256M
在我们周围，有很多令人惊叹的循环现象，比如四季的更替，生命的轮回，以及社会的发展。这些循环，或长或短，但都蕴含着一定的规律。
小码哥是个喜欢探索规律的人。一天，他发现一个有趣的数学现象: 整数的正整数次幂在某一位数上的重复性。
对于数字2来说:他的整数次幂为 21 = 2,22 = 4,23 = 8,24 = 16,25 = 32,2 = 64,...，它的个位数会呈现出一个循环的规律:2，4，8，6，2，4，8，6....如此循环往复，我们去掉重复的数，所以对于 2的正整数次幂，周期长度为 4(2，4，8，6)。其它整数的正整数次幂在个位数上也有类似的循环现象，它们的周期长度各不相同:
对于数字2，整数2的正整数次幂的前5个结果:2，4，8，16，32 循环的最后一位2,4,8,6，所以循环长度为4;
对于数字3，整数3的正整数次幂的前5个结果:3，9，27，81,243 循环的最后一位3,9,7,1，所
//
// Created by abner on 2023/12/20.
//
#include <bits/stdc++.h>
using namespace std;
int k;
char str[205];
struct bignum{
int x[205];
bignum(){memset(x,0,sizeof(x));}
}n,tmp,mul,ans;
bignum operator*(bignum a,bignum b)
{
bignum ans;
for (int i = 0;i<k;i++)
for (int j =0;j < k;j++)
ans.x[i +j] += a.x[i] * b.x[j];
for(int i=0;i<k;i++)
ans.x[i + 1]+= ans.x[i]/10,ans.x[i] %= 10;
for (int i = k;i<205;i++)
ans.x[i]=0;
return ans;
}
bignum operator*(bignum a,int b)
{
for (int i=0;i<=200;i++)
a.x[i]*=b;
for (int i=0;i<=200;i++)
a.x[i+1]+=a.x[i]/10,a.x[i]%=10;
return a;
}
int main(){
cin >>str >>k;
ans.x[0]=1;
int len = strlen(str);
for (int i = 0;i<k;i++)
n.x[i] = str[len -i-1]-'0';
mul = n;
for (int i=0;i<k;i++){
bignum tmp = n;
int j=1,flag = 1;
for(j=1;j<=10;j++){
tmp = tmp * mul;
if (tmp.x[i]==n.x[i]){
ans = ans * j;
flag = 0;
break;
}
}
if (flag) {
cout << -1;
return 0;
}
tmp = mul;
for (int k = 1;k < j;k++)
mul = mul * tmp;
}
len=200;
while (ans.x[len]==0 && len >= 1)
len--;
for (;len >=0;len--){
char aa = ans.x[len]+'0';
cout << aa;
}
return 0;
}本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- 码农的周末日常---2024/1/6
- 文心一言 vs. ChatGPT：哪个更胜一筹？
- 蓝桥杯省赛无忧 STL 课件17 map
- MySQL深入——15
- 【leetcode】搜索旋转排序数组 二分法变形
- CSDN : Armv8/Armv9架构从入门到精通二期-课程介绍
- 芯课堂 | 一种带WIFI的智能多电机控制系统
- Flutter GetX 之 国际化
- P40Recurrent Neural Network
- Git使用