你可以做很多事情。首先 - 请注意以奇数结尾的立方体必须以奇数开始 - 所以只尝试 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 次之后） - 大约需要 20 微秒才能找到 M 一次......注意 - 更新的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);
}