首页 > 代码库 > HDU 4228 Flooring Tiles 反素数的应用

HDU 4228 Flooring Tiles 反素数的应用

2024-07-11 13:33:57   219人阅读

给你一个数N，找出一个最小的可以拆分成N种乘积表达形式的数x

比如N=2，6可以拆成2x3或者1x6两种，但不是最小的，最小的是4可以拆成1x4,2x2两种

首先可以肯定的是x必然有N*2或者是N*2-1（完全平方的情况）个约数

利用求反素数的过程求出约数为N*2和N*2-1个的最小的数

#include <cstdio>#include <sstream>#include <fstream>#include <cstring>#include <iostream>#include <algorithm>#include <map>#include <cctype>#include <ctime>#include <set>#include <climits>#include <vector>#include <queue>#include <stack>#include <cstdlib>#include <cmath>#include <string>#include <list>#define INPUT_FILE "in.txt"#define OUTPUT_FILE "out.txt"using namespace std;typedef unsigned long long LL;const int INF = INT_MAX / 2;const LL maxval = 1e18 + 1;const int maxn = 75 + 5;const int maxcnt = 160;LL cnt[maxn * 2];int prime[20] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};int times[20];void dfs(LL curnum,LL curcnt,int nowt) {    if(curnum > maxval) return;    if(curcnt <= maxcnt) {        cnt[curcnt] = min(cnt[curcnt],curnum);    }    for(int i = 1;i <= maxcnt;i++) {        if(nowt == 0 || i <= times[nowt - 1]) {            curnum *= prime[nowt];             if(curnum > maxval) break;            curcnt = curcnt / i * (i + 1);            times[nowt] = i;            dfs(curnum,curcnt,nowt + 1);        }        else break;    }}int main() {    for(int i = 1;i <= maxcnt;i++) cnt[i] = maxval;    dfs(1,1,0);    int N;    while(cin >> N,N) {        LL a1 = cnt[N * 2 - 1],a2 = cnt[N * 2],sa = sqrt(a1);        if(sa * sa == a1 && a1 < a2) cout << a1 << endl;        else cout << a2 << endl;    }    return 0;}


联系
我们