【题目】如果正整数可以被 A 或 B 整除，那么它是神奇的。
返回第 N 个神奇数字。由于答案可能非常大，返回它模 10^9 + 7 的结果。
示例 1：
输入：N = 1, A = 2, B = 3 输出：2 示例 2：
输入：N = 4, A = 2, B = 3 输出：6 示例 3：
输入：N = 5, A = 2, B = 4 输出：10 示例 4：
输入：N = 3, A = 6, B = 4 输出：8 提示：
1 <= N <= 10^9 2 <= A <= 40000 2 <= B <= 40000
链接：https://leetcode-cn.com/problems/nth-magical-number
解法：提示，主要考虑周期性，N值很大，直接循环容易超时，解法的关键在于找到循坏的周期性，减少循环次数。另外需要考虑数值范围过大溢出的问题，用64位数据类型。
【源码】
int nthMagicalNumber(int N, int A, int B){ int index = 0; int64_t next = A; int64_t tmpA,tmpB; int d; int lastFlag; if (A==B) { int64_t NN = N; int64_t sum = (A*NN)%(1000000007); return (int)sum; } tmpA = A; tmpB = B; d=A-B; lastFlag = A<=B?0:1; int a=A,b=B; //找最大公约数 while(b>0) { int c= a; a = b; b = c%b; } int64_t tt=(N-1)/(A/a+B/a-1); N=(N-1)%(A/a+B/a-1)+1; if(tt>0) { tmpA = (A*B/a)*tt+A; tmpB = (A*B/a)*tt+B; d=(int)(tmpA-tmpB); } while(index++<N) { if (d<=0) { lastFlag = 0; if (d==0) { tmpB += B; d-=B; } tmpA+=A; d+=A; } else { lastFlag = 1; tmpB+=B; d-=B; } } if (lastFlag==0) { next = tmpA-A; } else { next = tmpB-B; } return next%(1000000007); }
