快速判断一个数能否被另一个数整除！

难得糊涂

如何快速判断一个大数能否被另一个大数整除！

小甲鱼

难得糊涂 发表于 2012-5-21 22:51

                               
登录/注册后可看大图

如果除数也是大数呢，也就是两个大数相除，可以显示商与余数，谢谢啊，纠结了好久！~

// 利用的是长除法的原理

void div(int a[100], int b[100], int c[100])
{
    int t[100];
    
    for (int i=100-1; i>=0; i--)
        for (int k=9; k>0; k--)     // 尝试商数
        {
            mul(b+i, k, t);
            if (largerthan(a+i, t))
            {
                sub(a+i, t, c+i);
                break;
            }
        }
}

void mul(int a[100], int b, int c[100])
{
    for (int i=0; i<100; i++)
        c[i] = a[i] * b;
                
    for (int i=0; i<100-1; i++) // 一口气进位
    {
        c[i+1] += c[i] / 10;
        c[i] %= 10;
    }
}

void sub(int a[100], int b[100], int c[100])
{
    for (int i=0; i<100; i++)
        c[i] = a[i] - b[i];
        
    for (int i=0; i<100-1; i++) // 一口气借位和补位
        if (c[i] < 0)
        {
            c[i+1]--;           // 借位
            c[i] += 10;         // 补位
        }
}

详细权威方案可以参考GMP的源代码，已经帮您分享出来：
http://bbs.fishc.com/thread-17779-1-1.html

友来友网

假设大数为m
另一个数为n

如果m%n == 0;  就能整除；

LOCK

#include "stdafx.h"
#include "iostream.h"
int main()
{
        int a,b;
        cin>>a>>b;
        if(a%b==0)
                cout<<"整除"<<endl;
        else
                cout<<"不能整除"<<endl;

        return 0;
}

小甲鱼

大数的除法与求余

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[1000],result[1000];
int main()
{
    long long mod,divis;
    int  n,i,k,flag,len;
    char c;
    while(cin>>s>>c>>n)   //输入被除数 s，符号 c （ '/' or ''% ），以及除数n
    {
        len=strlen(s);
        if(c=='%')
        {
            mod=0;
            for(i=0; i<len; i++)
            {
                mod=mod*10+s[i]-'0';          
                mod=mod%n;                      //利用除法性质，其实质是每次都是一个最多比n多一位的mod对n进行求余
            }
            cout<<mod<<endl;
        }
        else
        {
            divis=flag=0;
            for(i=k=0; i<len; i++)              
            {
                divis=divis*10+s[i]-'0';
                if(divis>=n&&!flag)                //利用除法性质，当divs大于除数n时，开始进行整除
                {
                    result[k++]=divis/n+'0';
                    divis=divis%n;                  //除法性质，余数*10加下一位的数字便是新的被除数
                    flag=1;
                }
                else if(flag)
                {
                    result[k++]=divis/n+'0';
                    divis=divis%n;
                }
            }
            if(!k) result[k++]='0';
            result[k]='\0';
            cout<<result<<endl;
        }
    }
    return 0;
}

难得糊涂

友来友网 发表于 2012-5-20 21:33

                               
登录/注册后可看大图

假设大数为m
另一个数为n

能这样算，就不是大数了，谢谢你！

难得糊涂

LOCK 发表于 2012-5-20 21:34

                               
登录/注册后可看大图

#include "stdafx.h"
#include "iostream.h"
int main()

大数能这样的！谢谢

难得糊涂

小甲鱼 发表于 2012-5-21 18:43

                               
登录/注册后可看大图

大数的除法与求余

如果除数也是大数呢，也就是两个大数相除，可以显示商与余数，谢谢啊，纠结了好久！~

y290176346

感谢楼主谢谢你 学习了

waliemiao

感谢楼主谢谢你 学习了