できることはたくさんあります。最初に - 奇数で終わる立方体は奇数として開始されたに違いないことに注意してください - したがって、M には奇数のみを試してください。時間を節約するには 2 倍にします。
次へ - 数字の下 3 桁を見つけるには、単にnumber % 1000. そして使用しないでくださいpow。非常に遅いです。数値の大きさを見つけるための私のトリックを参照してください。
次のような結果になります。
long int N, M, div;
printf("what is the value of N?\n");
scanf("%d", &N);
// test that it is reasonable before continuing...
// I did not write that code, but you should (size of N, and does it end in 1, 3, 7, or 9?
// find out how many digits N has:
div = 1;
while(N / div > 0) {
div *= 10;
}
// now loop around odd M
for(M = 1; M < div; M+=2) {
if( (M*M*M)%d==N) break;
}
// when you come out of this loop, M is the number you were looking for.
最後の微調整 - 数の立方体を見てください。
1*1*1 = 1
3*3*3 = 27
7*7*7 = 343
9*9*9 = 729
Nこのことから、 で終わる場合、 で終わる1数字だけをチェックできると結論付け1ます。
for(M=1; M<div; M+=10) {
他の値についても同様です (3 - M=7 で開始; 7 - M=3 で開始; 9 - M=9 で開始)。これで、コードが 10 倍速くなりました...
競争に勝つには十分ではないかもしれませんが、役立つはずです...
EDITは次のコードを実行しただけで、0.02秒で上記と同じ答えが得られました（アルゴリズムを10,000回回った後）-Mを1回だけ見つけるのに約20マイクロ秒です...注-m1配列を更新したので、コードはで終わる「有効な」数字の場合5(数字が存在するという保証はありませんが、1、3、7、および 9 で終わる数字について明示的に尋ねられた質問です)。
#include <stdio.h>
#include <time.h>
int main(void) {
long long int N, M, div;
long long int m1[] = {0, 1, 0, 7, 0, 5, 0, 3, 0, 9};
time_t start, end;
int ii;
printf("what is the value of N?\n");
scanf("%lld", &N);
// test that it is reasonable before continuing...
// I will leave that for you to do
start = clock();
// now starts the main loop
// I go around it 10,000 times to get a "reasonable accuracy" since the clock()
// function is not very granular (it was giving me "elapsed time zero")
// obviously for competition you want to do this just once!
for (ii = 0; ii < 10000; ii++) {
// find out how many digits N has:
div = 1;
while(N / div > 0) {
div *= 10;
}
// now try possible values of M - given the last digit of N
// we know what the last digit of M should be
// so we can start with that number, then take steps of 10
for(M = m1[N % 10]; M < div; M+=10) {
if( ( M * M * M ) % div == N ) break;
}
} // do it 10,000 times to get some time on the clock
// when you come out of this loop, M is the number you were looking for.
// since the loop stops at div, it should never be larger than N
printf("M is now %lld\n", M);
printf("M cubed is %lld which ends in %lld\n", M * M * M, ( M * M * M ) % div);
end = clock();
printf("Time taken: %f sec\n", ((float)(end - start) ) / CLOCKS_PER_SEC);
}