反素數的定義：
對于任何正整數
數
或者：
一個[1,n]的連續區間, 約數相同的最小數x，x是反素數，例如：f(6) = 4,f(8) = 4,6是約數為4切最小的數，所以6是約數，
反素數性質：
- 反素數肯定是從2開始的連續素數的冪次形式的乘積，
- 數值小的素數的冪次大于等于數值大的素數，即
中，有
性質的決議：
根據 反素數定義：
對于性質二： （5^6）*（7^2）*（11^7） > （5^7）*（7^6）*（11^2）
對于性質一：（5^7）*（7^6）*（11^2） > （2^7）*（3^6）*（5^2）
例題：反素數模板題
我們先求出這個區間最多由幾個素數相乘，即，(k1 = k2 = k3 = ... = kn , kn = 1)
我們再求出這個區間的最大數最多是最小素數的幾次冪， 2e9 < 2^30，
1 #include <iostream> 2 #include <cstdio> 3 #define ll long long 4 5 using namespace std; 6 7 int p[] = {2,3,5,7,11,13,17,19,23,29}; 8 int Max,ans,n; 9 10 // inx 素數下標 v當前數值 cnt 約數個數 pw之前的冪次 11 void dfs(int inx, int v, int cnt, int pw){ 12 13 for(int i = 1; i <= pw; ++i){ 14 if((ll)v * p[inx] > (ll)n){ 15 if(Max < cnt * i){ 16 Max = cnt * i; 17 ans = v; 18 19 }else if(cnt * i == Max) ans = min(ans, v); 20 break; 21 } 22 else dfs(inx + 1, v *= p[inx], cnt * (i + 1), i); 23 24 } 25 } 26 27 28 int main(){ 29 30 while(~scanf("%d", &n)){ 31 Max = 1; 32 dfs(0, 1, 1, 30); 33 printf("%d\n", ans); 34 } 35 36 return 0; 37 } 38
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/69641.html
標籤：其他
上一篇：動態規劃刷題