c++ - 关于迭代次数的任务

Question

有一个数N每次迭代它变得等于 (N*2)-1我需要找出多少步数将是原始 N 的倍数；

( 1≤ N ≤ 2 · 10 9 )

例如:

N = 7; count = 0

N_ = 7*2-1 = 13; count = 1; N_ % N != 0

N_ = 13*2-1 = 25; count = 2; N_ % N != 0

N_ = 25*2-1 = 49; count = 3; N_ % N == 0 

答案是3

如果这样无法分解，则输出-1

       #include <iostream> 
       using namespace std;

       int main(){
           int N,M,c;
           cin >> N;
           if (N%2==0) {
               cout << -1;
               return 0;
           }
           M = N*2-1;
           c = 1;
           while (M%N!=0){
               c+=1;
               M=M*2-1;
           }
           cout << c;
           return 0;
       }

它在(1 秒限制)期间不适合。如何优化算法？

P.S 所有提示的答案都是优化过的，但是1秒装不下，因为原则上需要改算法。解决方案是使用欧拉定理。

Answer 1

正如其他答案所暗示的那样，该问题等同于找到 c 使得 pow(2, c) = 1 mod N。如果 N 是偶数，这是不可能的，否则是可能的(正如您的代码表明您知道的那样)。

线性时间方法是:

int c = 1;
uint64_t m = 2;
while (m != 1){
  c += 1;
  m = (2*m)%N;
}
printf("%d\n", c);

要在 1 秒内解决这个问题，我认为您不能使用线性时间算法。最坏的情况是 N 是素数且很大。例如 1999999817，上面的代码在我的笔记本电脑上运行大约 10 秒。

相反，将 N 分解为质因数。对每个质因数求解 2^c = 1 mod p^k(其中 p^k 出现在 N 的质因式分解中。然后使用中国剩余定理合并结果。

当为给定的素数幂求c时，如果k=1，则解为c=p-1。当k比较大的时候，细节比较乱，不过你可以在这里找到一个书面的解决方案:https://math.stackexchange.com/questions/1863037/discrete-logarithm-modulo-powers-of-a-small-prime