针对CSP-J/S的冲刺练习:Day 1 基础题

发布时间:2024年01月01日

一、审题

时间限制:1000ms????????????????内存限制:256MB????????????????AC率:58.29%

题目描述

给定n个正整数,每个正整数都包含若干种质因子,现在小明想知道,这些质因子中,哪种质因子出现的次数最多(注意,每个数字中出现的每种质因子只统计一次)?

输入描述

输入数据共两行。第一行包含一个整数n,表示数字个数。

第二行包含以空格隔开的n个整数,每个数字在2~100000之内。

输出描述

输出一个正整数,表示出现最多的质因子,如果有多个质因子出现一样多,输出最小的那一个。

样例

输入

4

2 6 8 10

输出

2

提示

1 <= n <= 1000

二、分析&初试

1. 初始化、输入。

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

int main()
{
    // 初始化
    int n; // n个数据
    int a[1005] = {}; // 存储数据
    int cnt[100005] = {}; // 桶的思想,存储每个质因子出现的个数
    
    // 输入
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        // 分解a[i]的质因数…
    }
    return 0;
}

2. 分解质因数。

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

int main()
{
    // 初始化
    int n; // n个数据
    int a[1005] = {}; // 存储数据
    int cnt[100005] = {}; // 桶的思想,存储每个质因子出现的个数
    
    // 输入
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        
        // 分解a[i]质因数
        for (int j = 1; j <= sqrt(a[i]); j++)
        {
            if (a[i] % j == 0)
            {
                cnt[j]++;
            }
            while (a[i] % j == 0)
            {
                a[i] /= j;
            }
        }
        if (a[i] > 1)
        {
            cnt[a[i]]++;
        }
    }
    return 0;
}

3. 打擂台。

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

int main()
{
    // 初始化
    int n; // n个数据
    int maxn = -1e8; // 出现次数最多的质因子
    int temp; // 临时存放下标
    int a[1005] = {}; // 存储数据
    int cnt[100005] = {}; // 桶的思想,存储每个质因子出现的个数
    
    // 输入
    cin >> n; 
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        
        // 分解a[i]质因数
        for (int j = 1; j <= sqrt(a[i]); j++)
        {
            if (a[i] % j == 0)
            {
                cnt[j]++;
            }
            while (a[i] % j == 0)
            {
                a[i] /= j;
            }
        }
        if (a[i] > 1)
        {
            cnt[a[i]]++;
        }
    }
    
    // 打擂台
    for (int i = 2; i <= 100000; i++)
    {
        if (cnt[i] > maxn)
        {
            maxn = i;
            temp = i;
        }
    }
    
    // 输出
    cout << temp;
    return 0;
}

文章来源:https://blog.csdn.net/joe_g12345/article/details/135327556
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。