BZOJ1053: [HAOI2007]反素數ant(爆搜)

来源:https://www.cnblogs.com/zwfymqz/archive/2018/07/08/9280821.html
-Advertisement-
Play Games

Description 對於任何正整數x,其約數的個數記作g(x)。例如g(1)=1、g(6)=4。如果某個正整數x滿足:g(x)>g(i) 0<i<x ,則稱x為反質數。例如,整數1,2,4,6等都是反質數。現在給定一個數N,你能求出不超過N的最大的反質數麽 ? 對於任何正整數x,其約數的個數記作 ...


Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 4163  Solved: 2485
[Submit][Status][Discuss]

Description

 

  對於任何正整數x,其約數的個數記作g(x)。例如g(1)=1、g(6)=4。如果某個正整數x滿足:g(x)>g(i) 0<i<x ,則稱x為反質數。例如,整數1,2,4,6等都是反質數。現在給定一個數N,你能求出不超過N的最大的反質數麽 ?

Input

  一個數N(1<=N<=2,000,000,000)。

Output

  不超過N的最大的反質數。

Sample Input

1000

Sample Output

840

HINT

 

Source

 

這題跟數論有啥關係?

好像就用到約數定理

然後一波爆搜就A了

一開始讀錯題了以為約數相同時求最大的wa了一發

 

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define LL long long 
#define int long long 
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int prime[MAXN], vis[MAXN], tot = 0;
void GetPrime(int N) {
    vis[1] = 1; prime[0] = 1;
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++tot] = i;
        for(int j = 1; j <= tot && prime[j] * i <= N; j++) {
            vis[i * prime[j]] = 1;
            if(!i % prime[j]) break;
        }
    }
}
int N, Ans = 0, Ansnum = 0;
void dfs(int i, LL sum, int num) {
    if(i > 16 || sum > N) return ;
    if((num > Ansnum) ||(num == Ansnum && sum < Ans)) Ans = sum, Ansnum = num;
    for(int j = 1; j <= 63 && sum * prime[i] <= N; j++) 
        dfs(i + 1, sum *= prime[i], num * (j + 1));
}
main() { 
#ifdef WIN32
    //freopen("a.in", "r", stdin);
#endif
    GetPrime(50);
    N = read();
    dfs(1, 1, 1);
    printf("%d", Ans);
    return 0;
} 

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 中午吃飯時看了一下陸毅版的《三國》,剛好看的是蜀軍缺糧,諸葛亮讓王平去劫司馬懿的糧。司馬懿看蜀軍用木牛流馬運量很方便,就搶了蜀軍的木牛流馬仿製了一批,結果司馬懿用它運糧時,被王平冒充司馬懿的人在驗糧時,對木牛流馬動了手腳,結果木牛流馬不能動彈了,被蜀軍把幾十萬擔的糧食搶走了。看到這裡的時候,我想到了 ...
  • 下麵是EXE代碼 ...
  • 模型概述 有一DAG,問最少加多少條邊能夠使圖強連通。 題目描述 一些學校連入一個電腦網路。那些學校已訂立了協議:每個學校都會給其它的一些學校分發軟體(稱作“接受學校”)。註意即使 B 在 A 學校的分發列表中, A 也不一定在 B 學校的列表中。 你要寫一個程式計算,根據協議,為了讓網路中所有的學 ...
  • Description 給定一個含有n個數的序列a[1],a[2],a[3]……a[n],程式必須回答這樣的詢問:對於給定的i,j,k,在a[i],a[i+1 ],a[i+2]……a[j]中第k小的數是多少(1≤k≤j-i+1),並且,你可以改變一些a[i]的值,改變後,程式還能針對改 變後的a繼續 ...
  • 前言 微服務概念已經非常流行,這影響了現在架構的思想潮流。 如今,使用spring cloud體系搭建微服務架構的公司越來越多,成本低,出線上產品快,模塊全,開源等原因未來可能更加流行。 一般,我們需要一個監控系統來監控應用的數據,比如記憶體,磁碟,線程情況,資料庫連接池,配置信息,jvm信息等等。 ...
  • 大家好,上篇文章為大家介紹了線程間通信和協作的一些基本方式,那這篇文章就來介紹一下經典的wait-notify機制吧。 什麼是wait-notify機制? 想象一下有兩個線程A、B,如果業務場景中需要這兩個線程交替執行任務(比如A執行完一次任務後換B執行,B執行完後再換A執行這樣重覆交替),之前的基 ...
  • 轉自:https://www.cnblogs.com/Lynn-Zhang/p/5377024.html C/C++程式編譯流程(預處理->編譯->彙編->鏈接) 程式的基本流程如圖: 1. 預處理 預處理相當於根據預處理指令組裝新的C/C++程式。經過預處理,會產生一個沒有巨集定義,沒有條件編譯指令 ...
  • 一、概念 先來整體的介紹一下這篇博文要介紹的幾個概念(Channel、ChannelHandler、ChannelPipeline、ChannelHandlerContext、ChannelPromise): Channel:Netty 中傳入或傳出數據的載體;ChannelHandler:Nett ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...