給你一個數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; }

轉載于:https://www.cnblogs.com/rolight/p/3836098.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的HDU 4228 Flooring Tiles 反素数的应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。