c – 找到可被1到N之间的所有数除除的最小数,Remainder = 0
发布时间:2020-12-16 09:58:11 所属栏目:百科 来源:网络整理
导读:找到可从1到N的所有数字整除的最小数字,不留任何余数.由于数字可能非常大,我们采用模数1000000007的答案. 我认为可以被1到N的所有数字整除的最小数字是LCM(1..N). 示例:对于N = 5,该最小数字将为60. 因为60是可被所有数字形式整除的最小数字(1-5). 但由于一
找到可从1到N的所有数字整除的最小数字,不留任何余数.由于数字可能非常大,我们采用模数1000000007的答案.
我认为可以被1到N的所有数字整除的最小数字是LCM(1..N). 示例:对于N = 5,该最小数字将为60. 因为60是可被所有数字形式整除的最小数字(1-5). 但由于一些奇怪的原因,它给了我大的N(1000)等错误的答案. 这是我试图实施的内容. #include <iostream> #include <vector> using namespace std; vector<long long> lcmArr; const long long mod = 1000000007; long long gcd(long long a,long long b){ if(b == 0) { return a; } return gcd(b,a%b); } long long lcmFumction(long long a,long long b) { return (a*b)/gcd(a,b); } int main() { lcmArr.clear();lcmArr.resize(1002); lcmArr[0] =0; lcmArr[1] = 1; for(int i =2; i <=1000; i++){ lcmArr[i] = lcmFumction(lcmArr[i-1],i)%mod; //cout<<lcmArr[i-1]<<" "; } int T; cin >> T; while(T--) { int N; cin>>N; cout<<lcmArr[N]<<"n"; } return 0; } 解决方法
问题是当你计算LCM时,你使用除法,
和 ((A/B)/C) mod M != (((A/B) mod M)/C)mod M 例如(10/5/2)%2!=((10/5)%2)/ 2)%2 您应该使用modular inverse来计算它. 关于模逆的一些解释. 如果我们有: (a * b)%m = 1,则b是a的模逆,如b%m =(1 / a)%m. 因此,如果我们需要计算(x / a)%m,我们可以使它成为(x * b)%m. 我们知道(A * B * C)%m =((A * B)%m)* C)%m,因此,在您的情况下,模块化逆会派上用场. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |