Zoj 2562 More Divisors (反素数)

- 日理万妓 2022-08-25 01:56 105阅读 0赞

题意：给定一个数n，求在n以内，一个数的约数最多，并且是最小的一个数。

关于反素数：

### 定义 ###

对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数.

### 性质 ###

性质一:一个反素数的质因子必然是从2开始连续的质数.

性质二:p=2^t1\*3^t2\*5^t3\*7^t4.....必然t1>=t2>=t3>=....

学习链接：http://blog.sina.com.cn/s/blog\_893f611401016h84.html

#include<cstdio>
    #include<cstring>
    using namespace std ;
    
    long long Max,best,n;
    int prime[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
    
    void DFS (long long sum,long long cur,int k,int t)
    {//sum当前约数的总个数，cur当前数值及所有素因子的乘积
    //k正在使用的素数，t当前素数可达到的最高幂次
        if (Max<sum)
        {
            Max=sum;
            best=cur;
        }
        if (sum==Max && cur<best)
            best=cur;
        if (k>14) return;
        long long tmp=cur;
        for (int i=1;i<=t;i++)
        {
            if (tmp*prime[k]>n) break;
            tmp*=prime[k];
            DFS(sum*(i+1),tmp,k+1,i);
        }
    }
    int main ()
    {
        while (~scanf("%lld",&n))
        {
            Max=best=1;
            DFS(1,1,0,50);
            printf("%lld\n",best);
        }
        return 0 ;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，105人围观）

还没有评论，来说两句吧...

相关阅读

相关 1025. Divisor Game

Alice and Bob take turns playing a game, with Alice starting first. Initially, there is

淡淡的烟草味﹌/ 2024年03月23日 12:16/ 0 赞/ 80 阅读

相关 A. Odd Divisor

[传送门][Link 1] include <bits/stdc++.h> define ll long long define ios ios

缺乏、安全感/ 2022年10月29日 01:51/ 0 赞/ 2 阅读

相关 Zoj 2562 More Divisors (反素数)

题意：给定一个数n，求在n以内，一个数的约数最多，并且是最小的一个数。关于反素数：定义对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4

- 日理万妓/ 2022年08月25日 01:56/ 0 赞/ 106 阅读

相关 uva 294 ——Divisors

题意：给定一个区间\[l,r\],然后问在该区间内谁的因子最多！思路：先大致分析一下，比如对于一个数12，那么可以拆分成2\2\3，就是对一个数分解质因数，然后你会

怼烎@/ 2022年08月09日 13:49/ 0 赞/ 4 阅读

相关 hdu--6069--Counting Divisors

Counting Divisors Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 524288/524

àì夳堔傛蜴生んèń/ 2022年06月10日 01:37/ 0 赞/ 112 阅读

相关反素数学习_The Most Complex Number

[题目链接][Link 1] 先说一下反素数:(引自百度百科) 基本概念定义对于任何正整数x,其约数的个数记做g(x).例如g(1)=

我就是我/ 2022年05月12日 22:10/ 0 赞/ 148 阅读

相关 1076B Divisor Subtraction

B. Divisor Subtraction time limit per test 2 seconds memory limit per test 256 megab

缺乏、安全感/ 2022年04月17日 04:40/ 0 赞/ 157 阅读

相关元素数组的反转 java

元素数组的反转 java package com.xzy; / 元素数组的反转 @author 娟娟

柔光的暖阳◎/ 2022年03月15日 09:22/ 0 赞/ 219 阅读

相关 198. 反素数（dfs）

题目链接：https://www.acwing.com/problem/content/description/200/ [![知识共享许可协议][80x15.png]][

柔情只为你懂/ 2021年10月29日 14:10/ 0 赞/ 273 阅读

相关 D - Two Divisors (素数筛)

[题目][Link 1] 首先：对于gcd有 gcd(a,b)=gcd(a+b,b) 且若gcd(a,b)=1, 则gcd(a,c)=gcd(a,c\b

「爱情、让人受尽委屈。」/ 2021年07月16日 11:42/ 0 赞/ 377 阅读