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

难得糊涂

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

小甲鱼

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

                               
登录/注册后可看大图

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

1. // 利用的是长除法的原理
   
2. 
   
3. void div(int a[100], int b[100], int c[100])
   
4. {
   
5.     int t[100];
   
6.    
   
7.     for (int i=100-1; i>=0; i--)
   
8.         for (int k=9; k>0; k--)     // 尝试商数
   
9.         {
   
10.             mul(b+i, k, t);
    
11.             if (largerthan(a+i, t))
    
12.             {
    
13.                 sub(a+i, t, c+i);
    
14.                 break;
    
15.             }
    
16.         }
    
17. }
    
18. 
    
19. void mul(int a[100], int b, int c[100])
    
20. {
    
21.     for (int i=0; i<100; i++)
    
22.         c[i] = a[i] * b;
    
23.                
    
24.     for (int i=0; i<100-1; i++) // 一口气进位
    
25.     {
    
26.         c[i+1] += c[i] / 10;
    
27.         c[i] %= 10;
    
28.     }
    
29. }
    
30. 
    
31. void sub(int a[100], int b[100], int c[100])
    
32. {
    
33.     for (int i=0; i<100; i++)
    
34.         c[i] = a[i] - b[i];
    
35.         
    
36.     for (int i=0; i<100-1; i++) // 一口气借位和补位
    
37.         if (c[i] < 0)
    
38.         {
    
39.             c[i+1]--;           // 借位
    
40.             c[i] += 10;         // 补位
    
41.         }
    
42. }
    
43. 
    
44. 
    

复制代码

详细权威方案可以参考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;
}

小甲鱼

大数的除法与求余

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<cstring>
   
4. using namespace std;
   
5. char s[1000],result[1000];
   
6. int main()
   
7. {
   
8.     long long mod,divis;
   
9.     int  n,i,k,flag,len;
   
10.     char c;
    
11.     while(cin>>s>>c>>n)   //输入被除数 s，符号 c （ '/' or ''% ），以及除数n
    
12.     {
    
13.         len=strlen(s);
    
14.         if(c=='%')
    
15.         {
    
16.             mod=0;
    
17.             for(i=0; i<len; i++)
    
18.             {
    
19.                 mod=mod*10+s[i]-'0';         
    
20.                 mod=mod%n;                      //利用除法性质，其实质是每次都是一个最多比n多一位的mod对n进行求余
    
21.             }
    
22.             cout<<mod<<endl;
    
23.         }
    
24.         else
    
25.         {
    
26.             divis=flag=0;
    
27.             for(i=k=0; i<len; i++)              
    
28.             {
    
29.                 divis=divis*10+s[i]-'0';
    
30.                 if(divis>=n&&!flag)                //利用除法性质，当divs大于除数n时，开始进行整除
    
31.                 {
    
32.                     result[k++]=divis/n+'0';
    
33.                     divis=divis%n;                  //除法性质，余数*10加下一位的数字便是新的被除数
    
34.                     flag=1;
    
35.                 }
    
36.                 else if(flag)
    
37.                 {
    
38.                     result[k++]=divis/n+'0';
    
39.                     divis=divis%n;
    
40.                 }
    
41.             }
    
42.             if(!k) result[k++]='0';
    
43.             result[k]='\0';
    
44.             cout<<result<<endl;
    
45.         }
    
46.     }
    
47.     return 0;
    
48. }

复制代码

难得糊涂

友来友网 发表于 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

感谢楼主谢谢你 学习了