C言語で1*p1^n*p2^n*p3^n (n>=0)を満たすk番目に小さい整数を求めたいです。

Question

前提・実現したいこと

1p1^np2^n*p3^n (n>=0) (p1,p2,p3は2<=p1,p2,p3<=7を満たす素数)を満たす整数を小さい順に並べk(1<=k<=1000)番目に小さい値をできるだけ計算量を少なく求めたいです。

具体例
p1=2,p2=3,p3=5,k=4のとき)

1番目 1p1^0p2^0p3^0 = 1
2番目 1p1^1p2^0p3^0 = 2
3番目 1p1^0p2^1p3^0 = 3
4番目 1p1^2p2^0p3^0 = 4
5番目 1p1^0p2^0*p3^1 = 5

となり、求める値は4

発生している問題・エラーメッセージ

下記ソースコードで実行したところ900番目あたりから計算量が多くなりすぎて、CPU占有率が100％に張り付いてしまいました。

該当のソースコード

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#pragma warning(disable : 4996) //_CRT_SECURE_NO_WARNINGS
int main(void) {
	int p1, p2, p3, k;
	long long int temp, res = 2;
	int cnt = 1;
	long long int data[1000];
	data[0] = 1;
	scanf("%d%d%d%d", &p1, &p2, &p3, &k);
	while (cnt <= k - 1) {
		temp = res;
		while (res % p1 == 0) {
			res = res / p1;
			if (res == 1)break;
		}
		while (res % p2 == 0) {
			res = res / p2;
			if (res == 1)break;
		}
		while (res % p3 == 0) {
			res = res / p3;
			if (res == 1)break;
		}
		if (res == 1) {
			data[cnt] = temp;
			cnt++;
		}
		res = temp + 1;
	}
	if (k ==1) {
		printf("%d\n", 1);
	}
	else {
		printf("%lld\n",data[k - 1]);
	}
	return 0;
}

試したこと

・上記コードではp1,p2,p3いづれの倍数にも当てはまらない数字をスキップしながら、dataに値を格納しています。

・その他考えたプログラムは3重ループを書いて1*p1^(0-n)*p2^(0-n)*p3^(0-n)のすべての組み合わせを求めた後にqsortして1000番目を求めようとしました。

しかし1000番目を求めるためにはかなり大きな配列を用意しなければいけないので、あまり有効な方法だとは思いません。

補足情報（FW/ツールのバージョンなど）

言語：C言語
OS：Windows8 64bit

Comments

[m.ts10806]

コードやエラーはマークダウンのcode機能を利用してご提示ください。
https://teratail.com/questions/238564

[swordone]

タイトルとコードでやってることが全然違うようですが？

[shiracamus]

> 1*2^n*3^n*5^n (n>=0) を満たす整数を小さい順に並べ1000番目に小さい値

n=0 が 1番小さな値
n=1 が 2番目に小さな値
:
n=999 が 1000番目に小さな値
では？

[otn]

> 1*2^n*3^n*5^n (n>=0) を満たす整数
とコードに乖離があるのですが、もしかして、
1*2^i*3^j*5^k (i,j,kは非負の整数) を満たす整数
ですか？
そもそも入力値が何者かも書いてないし。
やりたいことを正しく書いてください。

[Tepura]

>>m.ts10806さん
マークダウンでコードを再掲致しました。

[Tepura]

>>shiracamusさん
質問内容を訂正いたしました。

[Tepura]

>>otnさん
1*p1^n*p2^n*p3^n (p1,p2,p3は2<=p1,p2,p3<=7を満たす素数)(nはn>=0を満たす正の整数)を満たす整数のうちk番目に小さい値を求めたいです。

[maisumakun]

C言語でなければならないですか？（C++など、他の言語は選べない状況ですか？）

[otn]

1*p1^n*p2^n*p3^n ではなく、1*p1^n1*p2^n2*p3^n3 と、べき数は異なるのでは？

1*p1^n*p2^n*p3^n とべき数が同じなら考えるまでも無く簡単。

Answer 1

データ構造を活用することで計算量・メモリ量を抑えて計算することが可能です。

(p1,p2,p3)=(2,3,5)の例で行くと、1→2→3→4→5→6→8→9→… という順になっており、
指数の組に直すと次のようになります。
(0,0,0)→(1,0,0)→(0,1,0)→(2,0,0)→(0,0,1)→(1,1,0)→(3,0,0)→(0,2,0)→…

ここで、例えば(1,1,0)は必ず(1,0,0)や(0,1,0)の後、(3,0,0)は(2,0,0)の後と言うように、「指数を+1しただけ」なら、必ず「元の数より後」になりますし、ある指数の組を考えるのは「指数を-1した組の後で良い」ということになります。

つまり、最初は(0,0,0)としたら次の候補は(1,0,0),(0,1,0),(0,0,1)だけ考えれば済みますし、(1,0,0)の次は候補に更に(2,0,0),(1,1,0),(1,0,1)を追加して考える、という感じです。
シミュレートしてみると次のようになります。

1st: (0,0,0) : 次の候補**(1,0,0),(0,1,0),(0,0,1)**
2nd: (1,0,0) : 次の候補(0,1,0),(0,0,1),(2,0,0),(1,1,0),(1,0,1)
3rd: (0,1,0) : 次の候補(0,0,1),(2,0,0),(1,1,0),(1,0,1),(0,2,0),(0,1,1)
4th: (2,0,0) : 次の候補(0,0,1),(1,1,0),(1,0,1),(0,2,0),(0,1,1),(3,0,0),(2,1,0),(2,0,1)
…

このように考えれば、次に来る数の候補の種類を最小限に抑えつつ、小さな順に列挙できます。

この時、候補を格納する配列を「ヒープ」という、最小または最大の値を容易に取り出せるデータ構造を使うと、計算量を抑えることができます。( C++なら priority_queue が該当します )
※もっとも、k=1000 程度なら、ヒープを使わなくてもそこまで遅くはならないと思います。

なお、上記シミュレートでは重複する候補を省いて書いていますが、プログラム上で重複にどう対処するかは検討の余地があると思います。

Comments

[Tepura]

angel_p_57さん

同じくベストアンサーに選びたいくらい詳細に解説していただきありがとうございました。
ヒープを使った解法も実際に実装氏てみようと思います。
ご指南感謝いたします。

Answer 2

※おそらく求められてるアルゴリズムとしては、otnさんがコメントで書いてあるものだと思うのでそれを前提にします。

まず前提としてx番目のp1^ip2^jp3^kを満たすような整数を考えると、i == j == k == 0である場合を除いて、同じようにp1,p2,p3の積で表せる数にp1かp2かp3を掛けることで作ることができます。
ということで、i == j == k == 0のパターンだけあらかじめ計算しておき、それ以降は小さいほうから順にあらかじめ計算済みのものを配列に記録していき、x番目の整数を求める場合にはそのなかからp1,p2,p3のいずれかをかけてx-1番目の整数より大きくなるもののうち最も小さいものを求めればいいだけです。
今回 k <= 1000程度なので二重ループで十分でしょう。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#pragma warning(disable : 4996) //_CRT_SECURE_NO_WARNINGS
int main(void) {
    int p1, p2, p3, k;
    long long int data[1000];
    data[0] = 1;
    scanf("%d%d%d%d", &p1, &p2, &p3, &k);
    int p[3] = {p1, p2, p3};
    for (int i = 1; i < k; ++i) {
        data[i] = data[i - 1] * p[0];//暫定値
        for (int j = 0; j < i; ++j) {
            for (int pi = 0; pi < 3; ++pi) {
                if (data[i - 1] < data[j] * p[pi] && data[j] * p[pi] < data[i]) {
                    data[i] = data[j] * p[pi];
                }
            }
        }
    }
    if (k ==1) {
        printf("%d\n", 1);
    }
    else {
        printf("%lld\n",data[k - 1]);
    }
    return 0;
}

※オーバーフローに関しては実際に計算して問題ない範囲であることは確認しました。
より大きなkに対しては、[0..x)の範囲が単調増加になってることを利用して二分探索を使うことも可能です。

Comments

[Tepura]

yudedako67さん

迅速にご回答いただき誠にありがとうございます！！
解法とソースがとても分かりやすかったのでベストアンサーにさせていただきました。
ご協力ありがとうございました！

Answer 3

ご提示のプログラムを基準に考えます。

scanf("%d%d%d%d", &p1, &p2, &p3, &k);

これでパラメータ4つが決まります。そうすると条件を満たす最大の整数は(p1p2p3)^kとなります。これを仮にXと置きましょう。条件を満たす各整数はXの約数と同値になります。また、この数は(1 + k)^3通りです。これを全て計算し、整列するのがもっとも単純な方法だと思います。

もっとも、kの大きさによっては非常に大きな計算リソースを要します。（課題文中ではkでなくn）

Comments

[Tepura]

HogeAnimalLoverさん

ご回答頂きありがとうございます。
私の質問の内容不足で誤解を招いてしまったかもしれません。
今回の問題では1*p1^i*p2^j*p3^s(i,j,s>=0)であり、同じ数で累乗するとは限らない設定でした。
ご協力頂きありがとうございました。（今後は質問の仕方に気を付けますm(__)m）