L1-080 乘法口诀数列 (20 分)-PAT 团体程序设计天梯赛 GPLT

本题要求你从任意给定的两个 1 位数字 a1和 a2 开始，用乘法口诀生成一个数列 {an}，规则为从 a1 开始顺次进行，每次将当前数字与后面一个数字相乘，将结果贴在数列末尾。如果结果不是 1 位数，则其每一位都应成为数列的一项。

输入格式：
输入在一行中给出 3 个整数，依次为 a1、a2 和 n，满足 0≤a1 ,a2≤9，0<n≤103。

输出格式：
在一行中输出数列的前 n 项。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：
2 3 10

输出样例：
2 3 6 1 8 6 8 4 8 4

样例解释：
数列前 2 项为 2 和 3。从 2 开始，因为 2×3=6，所以第 3 项是 6。因为 3×6=18，所以第 4、5 项分别是 1、8。依次类推…… 最后因为第 6 项有 6×8=48，对应第 10、11 项应该是 4、8。而因为只要求输出前 10 项，所以在输出 4 后结束。

分析：用A[i]表示数列的第i项，用last表示当前空着的位置，用sum表示第i项与第i+1项的乘积，如果大于10，则需要用两个位置来储存，最后输出前n项～

#include <bits/stdc++.h>
using namespace std;
int A, B, flag, num[10001], notIndep[10001];
bool isPrime(int a) {
    if (a == 1) return false;
    for (int i = 2; i <= sqrt(a); i++)
        if (a % i == 0) return false;
    return true;
}
bool isIndep(int x) {
    set<int> mark;
    int X = x, temp1, temp2;
    while (X != 1) {
        mark.insert(X);
        temp1 = 0;
        while (X) {
            temp2 = X % 10;
            X /= 10;
            temp1 += temp2 * temp2;
        }
        num[x]++;
        notIndep[temp1] = 1;
        X = temp1;
        if (mark.count(X)) return false;
    } 
    return true;
}
int main() {
    cin >> A >> B;
    vector<int> ans;
    for (int i = A; i <= B; i++)
        if (isIndep(i)) ans.push_back(i);
    for (int i = 0; i < ans.size(); i++) {
        if (isPrime(ans[i])) num[ans[i]] <<= 1;
        if (!notIndep[ans[i]]) {
            cout << ans[i] << ' ' << num[ans[i]] << endl;
            flag = 1;
        }
    }
    if (!flag) cout << "SAD"; 
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int A, B, flag, num[10001], notIndep[10001];

bool isPrime(int a) {

if (a == 1) return false;

for (int i = 2; i <= sqrt(a); i++)

if (a % i == 0) return false;

return true;

}

bool isIndep(int x) {

set<int> mark;

int X = x, temp1, temp2;

while (X != 1) {

mark.insert(X);

temp1 = 0;

while (X) {

temp2 = X % 10;

X /= 10;

temp1 += temp2 * temp2;

}

num[x]++;

notIndep[temp1] = 1;

X = temp1;

if (mark.count(X)) return false;

}

return true;

}

int main() {

cin >> A >> B;

vector<int> ans;

for (int i = A; i <= B; i++)

if (isIndep(i)) ans.push_back(i);

for (int i = 0; i < ans.size(); i++) {

if (isPrime(ans[i])) num[ans[i]] <<= 1;

if (!notIndep[ans[i]]) {

cout << ans[i] << ' ' << num[ans[i]] << endl;

flag = 1;

}

if (!flag) cout << "SAD";

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版