hiho一下第89周《Divisors》题目分析

20
13

题目大意

给定一个N，求不超过N的正整数中因子最多的数。如果有多个答案，输出最小的一个。

解题思路

本题是一道搜索题。

首先我们需要知道一个求因子个数的定理：

假设正整数n质因子分解为：

n = p1^n1 * p2^n2 * p3^n3 * ... * pk^nk

其中pi表示质因子，ni表示该质因子的数量，则有n的因子个数为：

D = (n1+1)*(n2+1)*(n3+1)* ... * (nk+1)

由此得到本题的一个基本解题思路：

枚举质因子数量，在使得n不超过N的情况下，使得D尽可能大


为了要D尽可能大，需要ni尽可能大，所以pi要尽可能小。

因此我们从最小的质数2开始枚举每一个质因子的数量ni，来计算n。

DFS(prime, now, divisors):
    If (prime > n) Then
        Return ;
    End If
    If (divisors > maxDivisors or
        (divisors == maxDivisors && now < result)
       ) Then
       maxDivisors = divisors
       result = now
    End If
    i = 0
    While (now * prime^i <= n) Then
        DFS(next_prime, now*prime^i,divisors*(i+1))
        i = i + 1
    End While


上面这段代码是可以计算出正确结果的，但是会严重的超时。因此我们还需要其他的剪枝，这里利用一个性质：

对最小解来说一定有：若pi和_pj_都属于n的质因子，且pi < pj，则一定有ni≥nj，其证明如下：

假设存在nj > ni，则有：。

n' = n / pj^(nj-ni) * pi(nj-ni)

n'的质因子个数和n相比，只是交换了ni和nj的值，因此D的值不会发生变化。 而由于pj > pi，因此 n' < n，所以 n 不是最小解。

同时由这个性质，我们可以知道当pi存在于n的质因子分解时(即ni≥1)，所有比pi小的质数一定也存在于n的质因子分解中。

所以我们推断出最大可能出现的质数为41，因为2~41之间的质数相乘刚好是小于10^16 ，若再乘上43，就会超过10^16。

由此得到改进后的搜索函数：

DFS(prime, now, divisors, lastNi):
    If (divisors > maxDivisors or
        (divisors == maxDivisors && now < result)
       ) Then
       maxDivisors = divisors
       result = now
    End If
    i = 1   
    // 由于使用了当前质数才能使用后面的质数，因此这个质数至少要使用1次
    While (now * prime^i < n && i <= lastNi) Then
        // 确保i小于等于上一个质数的数量
        DFS(next_prime, now*prime^i,divisors*(i+1), i)
        i = i + 1
    End While

使用该剪枝后，该题也就能很快的计算出正确结果了。

为了方便，需要事先将41以内的质数都找出来，这里可以使用常用的质数判定方法，或者干脆将这一段的质数表以const数组的方式保存。

还有点需要注意的是，在计算过程中可能出现溢出的情况，需要进行处理。

17 answer(s)

1

要且只要取11个质数！ 要且只要取11个质数！ 要且只要取11个质数！ 唉，分别取15,12,10个质数两次T，一次WA，G++交成GCC两次CE，A的好痛苦，有一种痛苦用言语表达不出。 得分 题目 结果 语言 时间 内存 提交时间 操作 100 / 100 Divisors AC G++ 1742ms 0MB 12秒前 查看 / 100 Divisors CE GCC 0ms 0MB 41秒前 查看 90 / 100 Divisors WA G++ 949ms 0MB 1分钟前 查看 90 / 100 Divisors TLE G++ 3018ms 0MB 1分钟前 查看 / 100 Divisors CE GCC 0ms 0MB 2分钟前 查看 70 / 100 Divisors TLE G++ 4410ms 0MB 4分钟前 查看

0 
#include<iostream>
#include<math.h>
using namespace std;


int prime_number[14] = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43, };
long long N;

int max_devisors;
long long number;


void DFS(long long now,int devisors,int prime_index, int ni) {
    if (now > N) {
        return;
    }
    if (devisors > max_devisors || (devisors == max_devisors && now < number)) {
        number = now;
        max_devisors = devisors;
    }
    for (int i = 1; i <= ni; i++) {
        long long newNumber = now*pow(prime_number[prime_index + 1],i);
        if (newNumber > N ) break;
        DFS(newNumber, devisors*(i + 1), prime_index + 1, i);
    }
}
int main() {
    cin >> N;
    max_devisors = 1;
    int a = log2(N);
    for (int i = 1; i <= a;i++)
        DFS(pow(2, i), i + 1, 0, i);
    cout << number << endl;

}

有一个没过是为什么？

1

第一次参赛，求问罚时是怎么计算的……

  • 从比赛开始到第一次AC的时间 + 20分钟 * 每次提交。简单来说就是越早AC越少提交罚时越短。

  • 添加评论
  • ✖reply
0

大数据没过。。用了longlong就好了。。

1

能不能讲解一下每一个变量的意义，prime now divisiors的意义。

  • prime （当前）质数，now 当前这个数， divisiors 当前这个数的因子个数

  • 添加评论
  • ✖reply
0

“对最小解来说一定有：若pi和pj都属于n的质因子，且pi < pj，则一定有ni≥nj”，根据这个性质能不能推出，只要求最大的m使n=2^m

  • 只要求最大的m使n=2^m<N，就行了？因为n'=pi^(ni+nj)小于n=pi^ni+pj^nj，所以只需要求有几个最小的质数2就可以了，我哪里理解错了吗？

  • 感觉你理解错了，2^m因子只有m+1个。

  • ”若pi和pj都属于n的质因子，且pi < pj，则一定有ni≥nj“是对可行解来说的，你说的”只要求最大的m使n=2^m“并不能得到一个可行解

  • 添加评论
  • ✖reply
1

为什么100以内的结果是60啊？表示没懂

  • 60的因子最多。

  • 60有哪些因子？才算最多，64有6个因子不算最多？不懂哪里理解错了

  • 64:1 2 4 8 16 32 64，只有7个 60:1 2 4;3 6 12;5 10 20;15 30 60,有12个

  • 添加评论
  • ✖reply
0

参考改进的搜索函数，加上了溢出判断，还是WA啊

  • 找到原因了，vs和g++给变量的初始值不同，然后我忘了初始化，导致素数数组求错。。。

  • 添加评论
  • ✖reply
0

// hih088.cpp : 定义控制台应用程序的入口点。 //

include "stdio.h"

include "math.h"

int commonisor(int commonisor,int divisors_array[],int divisors_array_count,int record_divisors_count[]); int main() { int input = 0; scanf_s("%d",&input);//存放输入数据 int divisors_array[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179 }; int record_divisors_count[sizeof(divisors_array)/sizeof(int)] = {0}; commonisor(input, divisors_array, sizeof(divisors_array) / sizeof(int), record_divisors_count); int *pointer = record_divisors_count;//使用指针指向数组，便于取值 int divisors_total=1; int size = sizeof(divisors_array)+(int)pointer; while ((int)pointer!=size) { divisors_total *= ((*pointer)+1); pointer++; } divisors_total *= 2;//因为最后一次没有记录质数数量，所以2被divisors_total printf("total:%d\n", divisors_total); while (getchar()!='q') { printf("input q to quit:"); } return 0; } void Find_divisors(int index,int record_divisors_count[]) { int * pointer= record_divisors_count;//用于指向数组中的任何位置 (*(pointer+index))++; } int commonisor(int common,int divisors_array[],int divisors_array_count,int record_divisors_count[]) { int index = 0; while (divisors_array[index] <= sqrt(common)&&index<= divisors_array_count-1) { if ((common % divisors_array[index]) == 0) { Find_divisors(index,record_divisors_count);//根据d使得Find_divisors中的数组找到对应位置添加此位置质数的数量 commonisor(common/ divisors_array[index], divisors_array, sizeof(divisors_array) / sizeof(int), record_divisors_count);//递归 return 0; } index++; } return 0;//到此，最后一次递归质数并没有记录，所以自动2被质数数量 }

0 
#include<iostream>
#include<string>
#include <math.h>
using namespace std;
int max_divisors;
long long result;
long long N;
int prime[14] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 ,43};
void DFS(long long now, int divisors, int prime_index, int ni)
{
    if (now > N) return;
    if (divisors > max_divisors || (divisors == max_divisors&&now < result))
    {
        max_divisors = divisors;
        result = now;
    }
    int i = 1;
    while ((now*pow(prime[prime_index], i)) <= N && i <= ni)
    {
        int newNumber=now*pow(prime[prime_index], i);
        DFS(newNumber, divisors*(i + 1), prime_index + 1, i);
        i++;
    }
}
int main()
{
    cin >> N;
    int a = log2(N);
    for (int i = 0; i <= a;i++)
    {
        DFS(pow(2, i), i + 1, 1, i);
    }
    cout << result << endl;
}

RE..错在哪里了？求问 VS上好好的。

0

&=1/4 设最小外积数为2同时也为最小正整数内的最小质数同时为自己质因数的数，则2a=px 所以a：px的2：1. 求得Px与外积数设为乘积为Ux的关系式为1：4（以2为例比例为2：1则以2为例子并且为存在最大质因数乘积的为Ux的关系为（1：2）/（2：1）假设x为4，则4*M(x-4)为那个正整数，则乘积为没有任何质因数的前四个质因数的乘积为1*5*7*11=156，因为所求为的质因数积数喂任意组合的乘积（算法略)因为1:4所以165/4=41.25，验证正整数42的前的质数的乘积为最大的质因数乘积而其中质因数个数为41，因为最小正整数为1，同时41.25又是以1为比例的结果，所以最大的正整数为41.

0

领教了。。。啥都不会，感觉自己就是一个战五渣啊== 上周的比赛也被虐得很惨T^T

0

24

0

我觉得4的原因就是 2.a=x
a=x分之2 因为a可以为1 所以 x=2分之1 设一个实数 2.实数b=实数y 则 2.b=2分之一乘以y b比上y=4分之1

所以 ab=x中 b:x=1:4 药ab=x要x最大同时ab最大则设a一定b需要最小 所以 当x=4的时候 ab=1*2*2 所以 需要有一组质因数 乘积正好是其中一个质因子的4倍

同时 此数分解的质因数又要最多 同时此数又是其中最小的一个数

则n个正整数中 bn:ym=1:4

an:m=a1:m=1:16:1:4=1:4 所以 an:a1=4:1

所以最大质因数应该是最小质因数的4倍所以 1,2,3,4=24

0

import java.util.Scanner; public class Main { public static void main(String[] args) { System.out.println("输入一个正整数"); Scanner cin = new Scanner(System.in); int n = cin.nextInt();

int b1,c,c1; c1=0; c=0; b1=1; for(int a=1;a<=n;a++) { int k=0; double j=Math.sqrt(a); for(int i=1;ic1) { b1=a; c1=c; }

} cin.close(); System.out.println("因子最多且最小的数为："+b1+"因子个数:"+c1); } }

0

#include

using namespace std;

int prime[14] = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43};

long long N,max_amount,out;

void dfs(long long num,int amount,int index) {

if (amount > max_amount || (amount == max_amount&& out > num)) {
    out = num;
    max_amount = amount;
}
if(index>13)return;
int i=1;while(1){
    num*=prime[index];i++;
    if(num>N)return;
    dfs(num,amount*i,index+1);
}

}

int main() {

cin >> N;
max_amount = 1;out=1;
dfs(1,1,0);
cout<<out<< endl;

}

1

怎么没人呢？这个网不火么？

  • 都在默默的写代码 学习

  • 你说得对，就是我这种辣鸡来评论

  • 因为大家都去leetcode或lintcode了，做的比这个oj友好多了，更适合普通人。。

  • 添加评论
  • ✖reply

write answer 切换为英文 切换为中文

转发分享

▲