寻找幸运数字的算法
我遇到了这个问题。如果数字的总和，以及数字的平方和是素数，则称为幸运数字。 A和B之间的幸运数字是多少？ 1 <= A <= B <= 10 18 。 我试过这个。
- 首先，我生成了1之间的所有可能素数和可以通过求和平方得到的数字（81 * 18 = 1458）。
- 我在A和B中读取了通过对数字求和可以生成的最大数量。如果B是2位数字（最大数字是由99生成的18）。
- 对于1和最大数之间的每个素数。 我应用了整数分区算法。
- 对于每个可能的分区，我检查了它们的数字的平方和是否形成素数。 如果是这样，则生成该分区的可能排列，如果它们位于范围内，则它们是幸运数字。
这是实施：
#include #include #include #include #include long long luckynumbers; int primelist[1500]; int checklucky(long long possible,long long a,long long b){ int prime =0; while(possible>0){ prime+=pow((possible%10),(float)2); possible/=10; } if(primelist[prime]) return 1; else return 0; } long long getmax(int numdigits){ if(numdigits == 0) return 1; long long maxnum =10; while(numdigits>1){ maxnum = maxnum *10; numdigits-=1; } return maxnum; } void permuteandcheck(char *topermute,int d,long long a,long long b,int digits){ if(d == strlen(topermute)){ long long possible=atoll(topermute); if(possible >= getmax(strlen(topermute)-1)){ // to skip the case of getting already read numbers like 21 and 021(permuted-210 if(possible >= a && possible <= b){ luckynumbers++; } } } else{ char lastswap ='\0'; int i; char temp; for(i=d;i n || numdigits > digits-1 || k > 9) return; if(k == n){ possible+=(k*getmax(numdigits)); findlucky(possible,a,b,digits); return; } partitiongenerator(k,nk,numdigits+1,(possible + k*getmax(numdigits)),a,b,digits); partitiongenerator(k+1,n,numdigits,possible,a,b,digits); } void calcluckynumbers(long long a,long long b){ int i; int numdigits = 0; long long temp = b; while(temp > 0){ numdigits++; temp/=10; } long long maxnum =getmax(numdigits)-1; int maxprime=0,minprime =0; temp = maxnum; while(temp>0){ maxprime+=(temp%10); temp/=10; } int start = 2; for(;start <= maxprime ;start++){ if(primelist[start]) { partitiongenerator(0,start,0,0,a,b,numdigits); } } } void generateprime(){ int i = 0; for(i=0;i<1500;i++) primelist[i] = 1; primelist[0] = 0; primelist[1] = 0; int candidate = 2; int topCandidate = 1499; int thisFactor = 2; while(thisFactor * thisFactor <= topCandidate){ int mark = thisFactor + thisFactor; while(mark <= topCandidate){ *(primelist + mark) = 0; mark += thisFactor; } thisFactor++; while(thisFactor <= topCandidate && *(primelist+thisFactor) == 0) thisFactor++; } } int main(){ char input[100]; int cases=0,casedone=0; long long a,b; generateprime(); fscanf(stdin,"%d",&cases); while(casedone < cases){ luckynumbers = 0; fscanf(stdin,"%lld %lld",&a,&b); int i =0; calcluckynumbers(a,b); casedone++; } } 算法太慢了。 我认为答案可以根据数字的属性找到。请分享你的想法。 谢谢。
优秀的解决方案OleGG，但您的代码未经过优化。 我对您的代码进行了以下更改，
-
在count_lucky函数中，它不需要通过9 * 9 * i来获取k，因为对于10000个情况，它会运行很多次，而不是我通过开始和结束减少了这个值。
-
我用ans数组来存储中间结果。 它可能看起来不多，但超过10000个案例，这是减少时间的主要因素。
我测试了这段代码，它通过了所有的测试用例。 这是修改后的代码：
#include const int MAX_LENGTH = 18; const int MAX_SUM = 162; const int MAX_SQUARE_SUM = 1458; int primes[1460]; unsigned long long dyn_table[20][164][1460]; //changed here.......1 unsigned long long ans[19][10][164][1460]; //about 45 MB int start[19][163]; int end[19][163]; //upto here.........1 void gen_primes() { for (int i = 0; i <= MAX_SQUARE_SUM; ++i) { primes[i] = 1; } primes[0] = primes[1] = 0; for (int i = 2; i * i <= MAX_SQUARE_SUM; ++i) { if (!primes[i]) { continue; } for (int j = 2; i * j <= MAX_SQUARE_SUM; ++j) { primes[i*j] = 0; } } } void gen_table() { for (int i = 0; i <= MAX_LENGTH; ++i) { for (int j = 0; j <= MAX_SUM; ++j) { for (int k = 0; k <= MAX_SQUARE_SUM; ++k) { dyn_table[i][j][k] = 0; } } } dyn_table[0][0][0] = 1; for (int i = 0; i < MAX_LENGTH; ++i) { for (int j = 0; j <= 9 * i; ++j) { for (int k = 0; k <= 9 * 9 * i; ++k) { for (int l = 0; l < 10; ++l) { dyn_table[i + 1][j + l][k + l*l] += dyn_table[i][j][k]; } } } } } unsigned long long count_lucky (unsigned long long maxp) { unsigned long long result = 0; int len = 0; int split_max[MAX_LENGTH]; while (maxp) { split_max[len] = maxp % 10; maxp /= 10; ++len; } int sum = 0; int sq_sum = 0; unsigned long long step_result; unsigned long long step_; for (int i = len-1; i >= 0; --i) { step_result = 0; int x1 = 9*i; for (int l = 0; l < split_max[i]; ++l) { //changed here........2 step_ = 0; if(ans[i][l][sum][sq_sum]!=0) { step_result +=ans[i][l][sum][sq_sum]; continue; } int y = l + sum; int x = l*l + sq_sum; for (int j = 0; j <= x1; ++j) { if(primes[j + y]) for (int k=start[i][j]; k<=end[i][j]; ++k) { if (primes[k + x]) { step_result += dyn_table[i][j][k]; step_+=dyn_table[i][j][k]; } } } ans[i][l][sum][sq_sum] = step_; //upto here...............2 } result += step_result; sum += split_max[i]; sq_sum += split_max[i] * split_max[i]; } if (primes[sum] && primes[sq_sum]) { ++result; } return result; } int main(int argc, char** argv) { gen_primes(); gen_table(); //changed here..........3 for(int i=0;i<=18;i++) for(int j=0;j<=163;j++) { for(int k=0;k<=1458;k++) if(dyn_table[i][j][k]!=0ll) { start[i][j] = k; break; } for(int k=1460;k>=0;k--) if(dyn_table[i][j][k]!=0ll) { end[i][j]=k; break; } } //upto here..........3 int cases = 0; scanf("%d",&cases); for (int i = 0; i < cases; ++i) { unsigned long long a, b; scanf("%lld %lld", &a, &b); //changed here......4 if(b == 1000000000000000000ll) b--; //upto here.........4 printf("%lld\n", count_lucky(b) - count_lucky(a-1)); } return 0; }
说明：
gen_primes（）和gen_table（）几乎是自我解释的。
count_lucky（）的工作原理如下：
拆分split_max []中的数字，只存储1，数十，数百等位置的单个数字。 这个想法是：假设split_map [2] = 7，所以我们需要计算结果
数百个位置，全部为00到99。
2在数百个位置，所有00到99。
。 。
数百个位置，全部为00到99。
这实际上是根据数字之和和已经预先处理的数字平方和来完成的（在l循环中）。 对于这个例子：总和将在0到9 *之间变化* i和平方和将在0到9 * 9 * i之间变化...这是在j和k循环中完成的。 对于i循环中的所有长度重复此操作
这就是OleGG的想法。
对于优化，考虑以下内容：
-
无用地运行从0到9 * 9 * i的平方和，对于特定的数字总和，它不会达到整个范围。 如果i = 3且sum等于5，则平方和将不会从0变化到9 * 9 * 3.此部分使用预计算值存储在start []和end []数组中。
-
特定数字位数和特定数字的值在数字的最重要位置和特定总和以及特定的平方和存储用于记忆。 它太长了但仍然大约45 MB。 我相信这可以进一步优化。
您应该使用DP执行此任务。 这是我的解决方案：
#include const int MAX_LENGTH = 18; const int MAX_SUM = 162; const int MAX_SQUARE_SUM = 1458; int primes[1459]; long long dyn_table[19][163][1459]; void gen_primes() { for (int i = 0; i <= MAX_SQUARE_SUM; ++i) { primes[i] = 1; } primes[0] = primes[1] = 0; for (int i = 2; i * i <= MAX_SQUARE_SUM; ++i) { if (!primes[i]) { continue; } for (int j = 2; i * j <= MAX_SQUARE_SUM; ++j) { primes[i*j] = 0; } } } void gen_table() { for (int i = 0; i <= MAX_LENGTH; ++i) { for (int j = 0; j <= MAX_SUM; ++j) { for (int k = 0; k <= MAX_SQUARE_SUM; ++k) { dyn_table[i][j][k] = 0; } } } dyn_table[0][0][0] = 1; for (int i = 0; i < MAX_LENGTH; ++i) { for (int j = 0; j <= 9 * i; ++j) { for (int k = 0; k <= 9 * 9 * i; ++k) { for (int l = 0; l < 10; ++l) { dyn_table[i + 1][j + l][k + l*l] += dyn_table[i][j][k]; } } } } } long long count_lucky (long long max) { long long result = 0; int len = 0; int split_max[MAX_LENGTH]; while (max) { split_max[len] = max % 10; max /= 10; ++len; } int sum = 0; int sq_sum = 0; for (int i = len-1; i >= 0; --i) { long long step_result = 0; for (int l = 0; l < split_max[i]; ++l) { for (int j = 0; j <= 9 * i; ++j) { for (int k = 0; k <= 9 * 9 * i; ++k) { if (primes[j + l + sum] && primes[k + l*l + sq_sum]) { step_result += dyn_table[i][j][k]; } } } } result += step_result; sum += split_max[i]; sq_sum += split_max[i] * split_max[i]; } if (primes[sum] && primes[sq_sum]) { ++result; } return result; } int main(int argc, char** argv) { gen_primes(); gen_table(); int cases = 0; scanf("%d", &cases); for (int i = 0; i < cases; ++i) { long long a, b; scanf("%lld %lld", &a, &b); printf("%lld\n", count_lucky(b) - count_lucky(a-1)); } return 0; }
简要说明：
- 我正在使用Eratosthenes方法计算高达9 * 9 * MAX_LENGTH的所有质数;
- 后来，使用DP，我正在构建表dyn_table，其中dyn_table [i] [j] [k]中的值X表示我们有正好X个长度为i的数字，其总和等于j ，其平方和等于k
- 然后我们可以轻松地计算从1到999..999（ len次数为9）的幸运数量。 为此，我们只总结所有dyn_table [len] [j] [k] ，其中j和k都是素数。
- 为了计算从1到随机X的幸运数量，我们将间隔从1到X分成长度等于10 ^ K的间隔（参见* count_lucky *函数）。
- 我们的最后一步是从count_lucky（b）中减去count_lucky（a-1） （因为我们在我们的间隔中包括一个 ）。
就这样。 O（log（MAX_NUMBER）^ 3）的预计算工作，每一步都有这种复杂性。
我已经针对线性直接测试我的解决方案，结果是相同的
而不是枚举数字空间，列举幸运数字的不同“签名”。 然后打印所有不同组合。
这可以通过简单的回溯来完成：
#define _GNU_SOURCE #include #include #include #include #include #define bitsizeof(e) (CHAR_BIT * sizeof(e)) #define countof(e) (sizeof(e) / sizeof((e)[0])) #define BITMASK_NTH(type_t, n) ( ((type_t)1) << ((n) & (bitsizeof(type_t) - 1))) #define OP_BIT(bits, n, shift, op) \ ((bits)[(unsigned)(n) / (shift)] op BITMASK_NTH(typeof(*(bits)), n)) #define TST_BIT(bits, n) OP_BIT(bits, n, bitsizeof(*(bits)), & ) #define SET_BIT(bits, n) (void)OP_BIT(bits, n, bitsizeof(*(bits)), |= ) /* fast is_prime {{{ */ static uint32_t primes_below_1M[(1U << 20) / bitsizeof(uint32_t)]; static void compute_primes_below_1M(void) { SET_BIT(primes_below_1M, 0); SET_BIT(primes_below_1M, 1); for (uint32_t i = 2; i < bitsizeof(primes_below_1M); i++) { if (TST_BIT(primes_below_1M, i)) continue; for (uint32_t j = i * 2; j < bitsizeof(primes_below_1M); j += i) { SET_BIT(primes_below_1M, j); } } } static bool is_prime(uint64_t n) { assert (n < bitsizeof(primes_below_1M)); return !TST_BIT(primes_below_1M, n); } /* }}} */ static uint32_t prime_checks, found; static char sig[10]; static uint32_t sum, square_sum; static void backtrack(int startdigit, int ndigits, int maxdigit) { ndigits++; for (int i = startdigit; i <= maxdigit; i++) { sig[i]++; sum += i; square_sum += i * i; prime_checks++; if (is_prime(sum) && is_prime(square_sum)) { found++; } if (ndigits < 18) backtrack(0, ndigits, i); sig[i]--; sum -= i; square_sum -= i * i; } } int main(void) { compute_primes_below_1M(); backtrack(1, 0, 9); printf("did %d signature checks, found %d lucky signatures\n", prime_checks, found); return 0; }
当我运行它时它会：
$ time ./lucky did 13123091 signature checks, found 933553 lucky signatures ./lucky 0.20s user 0.00s system 99% cpu 0.201 total
您希望生成所有可以使用该数字构建的数字的不同排列，而不是找到++。 我还预先计算了第一个1M的素数。
我没有检查代码是否100％正确，您可能需要调试一下。 但是这个想法就在这里，我能够产生0.2秒以下的所有幸运排列（即使没有错误也不应该超过两倍）。
当然，您希望生成validationA <= B的排列。您可能希望忽略生成数字多于B或小于A的分区。 无论如何，你可以从这里改进我的总体思路。
（注意：一开始的模糊是因为我剪切并粘贴了我为项目euler编写的代码，因此非常快的is_prime适用于N <= 1M;））
对于那些不知道的人来说，这是InterviewStreet.com网站上的一个问题（在我看来，这是最困难的一个）。 我的方法与OleGG的下方相似（并受其启发）。 然而，在创建了他所做的第一个[19] [163] [1459]表之后（我称之为table1），我的方向略有不同。 我创建了第二个粗糙长度表[19] [x] [3]（表2），其中x是相应位数的唯一和对的数量。 对于表的第三维，长度为3，第一个元素是唯一“和对”的数量，其中sum和squareSum值由第二和第三个元素保持。
例如：
//pseudocode table2[1] = new long[10][3] table2[1] = {{1, 0, 0}, {1, 1, 1}, {1, 2, 4}, {1, 3, 9}, {1, 4, 16}, {1, 5, 25}, {1, 6, 36}, {1, 7, 49}, {1, 8, 64}, {1, 9, 81}} table2[2] = new long[55][3] table2[3] = new long[204][3] table2[4] = new long[518][3] . . . . table2[17] = new long[15552][3] table2[18] = new long[17547][3]
可以通过查询table1来validation对于arrays的第二维长度（10,55,204,518，…，15552,17547）具有的数字，并且可以以类似的方式填充表2。 现在使用table2，我们可以比OleGG发布的方法更快地解决大的“幸运”查询，尽管他仍然使用类似的“拆分”过程。 例如，如果您需要找到幸运（00000-54321）（即0到54321之间的幸运数字），它会分解为以下5行的总和：
lucky(00000-54321) = { lucky(00000-49999) + lucky(50000-53999) + lucky(54000-54299) + lucky(54300-53319) + lucky(54320-54321) }
哪个进一步分解：
lucky(00000-49999) = { lucky(00000-09999) + lucky(10000-19999) + lucky(20000-29999) + lucky(30000-39999) + lucky(40000-49999) } . . lucky(54000-54299) = { lucky(54000-54099) + lucky(54100-54199) + lucky(54200-54299) } . . . etc
通过查询table2可以轻松获得这些值中的每一个。 例如，通过将4和16添加到第三维表2的第2和第3个元素中找到lucky（40000-49999）：
sum = 0 for (i = 0; i < 518; i++) if (isPrime[table2[4][i][1] + 4] && isPrime[table2[4][i][2] + 4*4]) sum += table2[4][i][0] return sum
或者为幸运（54200-54299）：
sum = 0 for (i = 0; i < 55; i++) if (isPrime[table2[2][i][1] + (5+4+2)] && isPrime[table2[2][i][2] + (5*5+4*4+2*2)]) sum += table2[2][i][0] return sum
现在，OleGG的解决方案比我之前尝试过的任何其他解决方案都要快得多，但是通过上面描述的修改，它比以前表现得更好（对于大型测试集来说，大约是100倍）。 但是，对于InterviewStreet上的盲测试案例，它仍然不够快。 通过一些聪明的黑客，我能够确定我目前正在运行大约20倍太慢，无法在规定的时间内完成测试集。 但是，我找不到进一步的优化。 这里最大的时间沉没显然是在遍历table2的第二维，并且避免这种情况的唯一方法是将这些总和的结果制成表格。 但是，有太多的可能性在给定的时间内（5秒）计算它们或将它们全部存储在给定的空间（256MB）中。 例如，上面的幸运（54200-54299）循环可以预先计算并存储为单个值，但如果是，我们还需要预先计算幸运（123000200-123000299）和幸运（99999200-99999299） ）等等。我已经完成了数学运算，预计算的计算量太多了。
我刚刚解决了这个问题。
这只是一个动态编程问题。 将DP[n](sum-square_sum)作为DP函数， DP[n](sum-square_sum)是所有数字小于或等于n的数字的计数，其中sum和square_sum为数字数字的数字分别用sum和square_sum表示。 例如：
DP[1](1-1) = 1 # only 1 satisfies the condition DP[2](1-1) = 2 # both 1 and 10 satisfies the condition DP[3](1-1） = 3 # 1 10 100 DP[3](2-4） = 3 # 11 110 101
由于我们可以很容易地找出第一个DP状态DP [1] [..] [..]，它是：
(0-0) => 1 (1-1) => 1 (2-4) => 1 (3-9) => 1 (4-16) => 1 (5-25) => 1 (6-36) => 1 (7-49) => 1 (8-64) => 1 (9-81) => 1
那么我们可以从DP [1]中推导出DP [1]，然后DP [3] … DP [18]上面的推论是由于每当n增加1时，例如来自DP [1] ]到DP [2]，我们得到一个新数字（0..9），并且必须更新（sum，square_sum）对（即DP [n]）的集合。
最后，我们可以遍历DP [18]设置和幸运数字的计数。
那么，上面算法的时间和空间复杂度怎么样？ 我们知道sum <= 18 * 9 = 162，square_sum <= 18 * 9 * 9 = 1458，所以（sum，square_sum）对的集合（即DP [n]）非常小，小于162 * 1458 = 236196，实际上它比236196小得多; 事实是：我的ruby程序计算0到10 ^ 18之间的所有幸运数字，不到1秒。
ruby lucky_numbers.rb 0.55s user 0.00s system 99% cpu 0.556 total
我通过使用powershell算法编写测试函数来测试我的程序，它适用于小于10 ^ 7的数字。
根据要求，您可以采用不同的方式。 如果我这样做，我会使用’Eratosthenes筛选’在所需范围（A到（9 * 2）* B.length）中计算素数，缓存它们（再次，根据您的设置，您可以使用-memory或disk cache）并将其用于下一次运行。
我只编写了一个快速解决方案（Java），如下所示（ 注意 ：不检查整数溢出。只是一个快速的例子。另外，我的代码没有优化。）：
import java.util.ArrayList; import java.util.Arrays; public class LuckyNumbers { public static void main(String[] args) { int a = 0, b = 1000; LuckyNumbers luckyNums = new LuckyNumbers(); ArrayList luckyList = luckyNums.findLuckyNums(a, b); System.out.println(luckyList); } private ArrayList findLuckyNums(int a, int b) { ArrayList luckyList = new ArrayList (); int size = ("" + b).length(); int maxNum = 81 * 4; //9*2*b.length() - 9 is used, coz it's the max digit System.out.println("Size : " + size + " MaxNum : " + maxNum); boolean[] primeArray = sieve(maxNum); for(int i=a;i<=b;i++) { String num = "" + i; int sumDigits = 0; int sumSquareDigits = 0; for(int j=0;j
输出是：
[11,12,14,16,21,23,25,32,38,41,49,52,56,58,61,65,83,85,94,101,102,104,106,110,111 ，113,119,120,131,133,137,140,146,160,164,166,173,179,191,197,199,201,203,205,210,223,229,230,232,250 ，289,292,298,302,308,311,313,317,320,322,331,335,337,344,346,353,355,364,368,371,373,377,379,380,386 ，388,397,401,409,410,416,434,436,443,449,461,463,467,476,490,494,502,506,508,520,533,535,553,559,560 ，566,580,595,601,605,610,614,616,634,638,641,643,647,650,656,661,665,674,683,689,698,713,719,731,733 ，737,739,746,764,773,779,791,793,797,803,805,829,830,836,838,850,863,869,883,892,896,904,911,917,919 ，922,928,937,940,944,955,968,971,973,977,982,986,991]
我没有仔细分析您当前的解决方案，但这可能会改善它：
由于数字的顺序无关紧要，您应该检查长度为1到18的数字0-9的所有可能组合，跟踪数字和它们的正方形的总和，并一次添加一个数字，使用之前的结果计算。
因此，如果您知道12位数字是3而正方形是5，请查看数字120,121,122 …等，并从3和5中为12计算它们的总和。
有时，最快的解决方案非常简单：
uint8_t precomputedBitField[] = { ... }; bool is_lucky(int number) { return precomputedBitField[number >> 8] & (1 << (number & 7)); }
只需修改现有代码即可生成“precomputedBitField”。
如果您担心大小，要覆盖从0到999的所有数字，它只需要花费125个字节，因此这种方法可能比任何其他替代方案更小（并且更快）。
我试图用Pierre的枚举方法提出一个解决方案，但从来没有想出一个足够快的方法来计算排列。 OleGG的计数方法非常聪明，盗版的优化是必要的，以使其足够快。 我提出了一个小的改进，一个解决一个严重的问题。
首先，改进：你不必逐步检查所有的总和和广场，检查盗版的j和k循环中的素数。 您有（或可以轻松生成）素数列表。 如果您使用其他变量来确定哪些素数在范围内，您可以单步执行sum和squaresum的合适素数列表。 一个素数数组和一个查询表，可以快速确定素数> =数字所在的索引是有用的。 然而，这可能只是一个相当小的改进。
最大的问题是盗版的ans缓存数组。 声称不是45MB; 64位条目，它是364MB。 这超出了（当前）允许的C和Java内存限制。 通过去掉“l”维度可以减少到37MB，这是不必要的，无论如何都会损害缓存性能。 你真的对l + sum和l * l + squaresum的缓存计数感兴趣，而不是单独的l，sum和squaresum。
首先，我想补充说，一个幸运数字可以用筛子计算，筛子的解释可以在这里找到： http ： //en.wikipedia.org/wiki/Lucky_number
这样您就可以使用筛子来确定数字，从而提高解决方案的速度，