算法来寻找幸运数字 [英] Algorithm to find Lucky Numbers
问题描述
我碰到这个question.A数称为幸运的，如果它的数字的总和，以及其位数的平方和是素数。多少数A和B之间是幸运的？ 1＆LT; = A＆LT; = B＆LT; = 10 18 。我想这一点。
I came across this question.A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between A and B are lucky? 1 <= A <= B <= 1018. I tried this.
- 首先，我产生1和号码之间的所有可能的素数是可以产生求和的平方（81 * 18 = 1458）。
- 在我读A和B找出可以求和数字生成最大数量。如果B是2位数字（最大号码18 99产生的）。
- 为1的最大数量之间的每一个素数。我申请的整数分区算法。
- 对于我检查了他们的数字平方的总和是否形成黄金每一个可能的分区。如果是这样产生的分区的可能的排列，如果他们趴在范围内，他们是幸运的数字。
这是实施
#include<stdio.h>
#include<malloc.h>
#include<math.h>
#include <stdlib.h>
#include<string.h>
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<strlen(topermute);i++){
if(lastswap == topermute[i])
continue;
else
lastswap = topermute[i];
temp = topermute[d];
topermute[d] = topermute[i];
topermute[i] = temp;
permuteandcheck(topermute,d+1,a,b,digits);
temp = topermute[d];
topermute[d] = topermute[i];
topermute[i] = temp;
}
}
}
void findlucky(long long possible,long long a,long long b,int digits){
int i =0;
if(checklucky(possible,a,b)){
char topermute[18];
sprintf(topermute,"%lld",possible);
permuteandcheck(topermute,0,a,b,digits);
}
}
void partitiongenerator(int k,int n,int numdigits,long long possible,long long a,long long b,int digits){
if(k > n || numdigits > digits-1 || k > 9) return;
if(k == n){
possible+=(k*getmax(numdigits));
findlucky(possible,a,b,digits);
return;
}
partitiongenerator(k,n-k,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++;
}
}
的算法是太慢了。我想答案可以根据numbers.Kindly的财产交流你的看法被发现。谢谢你。
The algorithm is too slow. I think the answer can be found based on the property of numbers.Kindly share your thoughts. Thank you.
推荐答案
优秀的解决方案OleGG，但你的code不被优化。我做了以下更改code，
Excellent solution OleGG, But your code is not optimized. I have made following changes to your code,
-
它不需要经过9 * 9 *我对K的count_lucky功能，因为10000情况下，它会运行多次，相反，我必须通过开始和结束降低这个值。
It does not require to go through 9*9*i for k in count_lucky function, because for 10000 cases it would run that many times, instead i have reduced this value through start and end.
我已经使用答阵列来存储中间结果。它可能貌不惊人，但超过10000情况下，这是主要因素，可以减少时间。
i have used ans array to store intermediate results. It might not look like much but over 10000 cases this is the major factor that reduces the time.
我已经测试了这个code，它通过了所有的测试案例。下面是修改code：
I have tested this code and it passed all the test cases. Here is the modified code:
#include <stdio.h>
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（）是pretty的多的自我解释。
gen_primes() and gen_table() are pretty much self explanatory.
count_lucky（）的工作原理如下：
count_lucky() works as follows:
分割数split_max []，只是存储的位，十位，百个位数的号码等职务。 我们的想法是：假设split_map [2] = 7，所以我们需要计算结果为
split the number in split_max[], just storing single digit number for ones, tens, hundreds etc. positions. The idea is: suppose split_map[2] = 7, so we need to calculate result for
1在百位，所有00至99分钟。
1 in hundreds position and all 00 to 99.
2的百位，所有00至99分钟。
2 in hundreds position and all 00 to 99.
。
7在百位，所有00至99分钟。
7 in hundreds position and all 00 to 99.
这是实际完成的（L中环）的数字总和这一直是precalcutaled数字平方和总和的。 在这个例子中：总和将变化从0到9 * I和平方和会有所不同，从0到9 * 9 * ...我这是在J和K循环中完成。 这被重复用于所有的长度在i循环
this is actually done(in l loop) in terms of sum of digits and sum of square of digits which has been precalcutaled. for this example: sum will vary from 0 to 9*i & sum of square will vary from 0 to 9*9*i...this is done in j and k loops. This is repeated for all lengths in i loop
这是OleGG的想法。
This was the idea of OleGG.
有关优化以下被认为是：
For optimization following is considered:
-
其用武之地，从0到9 * 9运行平方和*我作为数字特别款项也不会去高达品种齐全。就像如果我= 3，和等于5，然后平方和不会从0到9 * 9 * 3，本部分改变都存储在启动[]和使用precomputed值结束[]数组。
its useless to run sum of squares from 0 to 9*9*i as for particular sums of digits it would not go upto the full range. Like if i = 3 and sum equals 5 then sum of square would not vary from 0 to 9*9*3.This part is stored in start[] and end[] arrays using precomputed values.
值的数字特定数量和特定位数最多显著多的位置，特别是高达之和高达方形isstored的记忆特别总和。它太长，但仍是其约45 MB。 我相信这可以进一步优化。
value for particular number of digits and particular digit at most significant position of number and upto particular sum and upto particular sum of square isstored for memorization. Its too long but still its about 45 MB. I believe this could be further optimized.
这篇关于算法来寻找幸运数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
