A50512. 循环数
填空题
困难
知识点
题目描述
循环数
题目描述
循环数是n位长度的整数，当乘以从1到n的任何整数时，产生原始数字的“循环”。也就是说，如果考虑最后一个数字之后的数字“绕”回到第一个数字，两个数字中的数字序列将是相同的，尽管它们可能从不同的位置开始。例如，数字142857是循环的，如下表所示：
142857 *1 = 142857
142857 *2 = 285714
142857 *3 = 428571
142857 *4 = 571428
142857 *5 = 714285
142857 *6 = 857142
编写一个程序来确定数字是否是循环数。
1
2
3
4
5
6
7
8
9
10
输入形式
输入一个数，长度在2到60位之间(请注意，前面的零不应该被删除，它们被认为是确定n的大小和计数的一部分，因此，“01”是一个两位数的数字，与“1”是一个一位数的数字不同。) 。
1
输出形式
对于每个输入，输出一行(Yes或No)标识它是否是循环数。
1
样例输入
142857
样例输出
Yes
参考答案
#include <bits/stdc++.h>
using namespace std;
set<string> strs;
string shift(string str,int n){
string newStr;
newStr = str.substr(str.size() - n, n) + str.substr(0, str.size() - n);
return newStr;
}
string multiplication(string str,int n){
char ans[62];
int num = 0;
int carry = 0;
for(int i = str.size() - 1; i >= 0; i--){
int temp = (str[i] - '0') * n;
ans[num++] = (temp + carry) % 10 + '0';
carry = (temp + carry) / 10;
}
if(carry != 0){
ans[num++] = carry + '0';
}
ans[num] = '\0';
for(int i = 0; i < num / 2; i++){
char t = ans[i];
ans[i] = ans[num - 1 - i];
ans[num - 1 - i] = t;
}
string newStr = ans;
return newStr;
}
int main(){
string a;
cin >> a;
for(int i = 0; i < a.size(); ++i){
string temp = shift(a, i);
strs.insert(temp);
}
bool flag = true;
for(int i = 1; i <= a.size(); ++i){
string temp = multiplication(a, i);
if(strs.count(temp) == 0){
flag = false;
break;
}
}
if(flag) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
上一题
下一题