加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

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,因此,在您的情况下,模块化逆会派上用场.

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读