难得糊涂 发表于 2012-5-20 18:14:02

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

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

小甲鱼 发表于 2012-5-20 18:14:03

难得糊涂 发表于 2012-5-21 22:51 static/image/common/back.gif
如果除数也是大数呢，也就是两个大数相除，可以显示商与余数，谢谢啊，纠结了好久！~// 利用的是长除法的原理

void div(int a, int b, int c)
{
    int t;
   
    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, int b, int c)
{
    for (int i=0; i<100; i++)
      c = a * b;
               
    for (int i=0; i<100-1; i++) // 一口气进位
    {
      c += c / 10;
      c %= 10;
    }
}

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


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

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

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

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

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

#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;
}

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


大数的除法与求余

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s,result;
int main()
{
    long long mod,divis;
    intn,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-'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-'0';
                if(divis>=n&&!flag)                //利用除法性质，当divs大于除数n时，开始进行整除
                {
                  result=divis/n+'0';
                  divis=divis%n;                  //除法性质，余数*10加下一位的数字便是新的被除数
                  flag=1;
                }
                else if(flag)
                {
                  result=divis/n+'0';
                  divis=divis%n;
                }
            }
            if(!k) result='0';
            result='\0';
            cout<<result<<endl;
      }
    }
    return 0;
}

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

友来友网 发表于 2012-5-20 21:33 static/image/common/back.gif
假设大数为m
另一个数为n



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

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

LOCK 发表于 2012-5-20 21:34 static/image/common/back.gif
#include "stdafx.h"
#include "iostream.h"
int main()


大数能这样的！谢谢

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

小甲鱼 发表于 2012-5-21 18:43 static/image/common/back.gif
大数的除法与求余

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

y290176346 发表于 2015-10-8 22:00:04

感谢楼主谢谢你 学习了

waliemiao 发表于 2015-10-9 01:29:57

感谢楼主谢谢你 学习了
页: [1]
查看完整版本: 快速判断一个数能否被另一个数整除！