站外题求解

原题链接
（核桃OJ比赛的题，结束后就变成这样了）：

题目描述

小一觉得约数个数很有趣，因为它并不是线性增长的。数字 5 是素数，只有 1, 5 两个因数，而比它更小的数字 4 拥有 1, 2, 4 三个因数。

将约数的个数记作，如果有某个正整数满足：，都有，则小一称为有趣数。

整数等都是有趣数。

现在给定一个数，你能求出不超过的最大的有趣数么？

输入格式

一个数。

输出格式

不超过的最大的有趣数。

有以下代码(95):

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a[20000005],k,m,s;
int main(){
    freopen("fun.in","r",stdin);
    freopen("fun.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>n;
    if(n==1){
        cout<<1;
        return 0;
    }
    m=n;
    for(int i=2;i<=m;i++)for(int j=2;j*i<=n;j++)a[i*j]++;
    for(int i=1;i<=n;i++){
        if(a[i]>s){
            s=a[i];
            k=i;
        }
    }
    cout<<k;
	return 0;
}

与以下代码(100):

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a[20000005],k,m,s;
int main(){
    freopen("fun.in","r",stdin);
    freopen("fun.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>n;
    if(n==1){
        cout<<1;
        return 0;
    }
    for(int i=2;i<=n;i++)for(int j=i;j<=n;j+=i)a[j]++;
    for(int i=1;i<=n;i++){
        if(a[i]>s){
            s=a[i];
            k=i;
        }
    }
    cout<<k;
	return 0;
}

它们的区别就是for(int j=2;j*i<=n;j++)a[i*j]++;变成了for(int j=i;j<=n;j+=i)a[j]++;。
所以第一种实现方法那有问题？

讨论操作

题目描述

输入格式

输出格式

回复

相关推荐

站外题求解