快速判斷一個(gè)整數(shù)能否被另一個(gè)整數(shù)整除

[info]

可能大家在小數(shù)初中的時(shí)候都知道一些快速判斷一個(gè)數(shù)能被特殊的數(shù)整除的方法，如：

如果一個(gè)數(shù)的所有數(shù)字之和能被3整除，則這個(gè)數(shù)能被3整除；

如果一個(gè)數(shù)的個(gè)位為0或5，則這個(gè)數(shù)能被5整除；

如果一個(gè)數(shù)的個(gè)位數(shù)加10位數(shù)的2倍加上百位數(shù)的4倍能被8整除，則這個(gè)數(shù)能被8整除

如果一個(gè)數(shù)的所有數(shù)字之和能被9整除，則這個(gè)數(shù)能被9整除；

如果一個(gè)數(shù)所有奇數(shù)位的數(shù)字相加減去所有偶數(shù)位的數(shù)字后的值能被11整除，那么這個(gè)數(shù)能被11整除；

但是如何快速判斷一個(gè)數(shù)能被7整除呢？本文進(jìn)行了被整除的理論深入分析。

設(shè)x和m是一個(gè)自然數(shù)： x=xn …. x3 x2 x1 x1為x的個(gè)位， x2為x的十位， x3為x的百位， xn為x的N位 如x=2368，則x1=8,x2=6,x3=3,x4=2 則有如下公式： x%m=( x1 +101%m*x2+102%m*x3+……+10n-1%m*xn)%m 其中%表示求余數(shù)的符號(hào) 公式證明 依據(jù)余數(shù)的兩個(gè)定理 (m+n)%k=(m%k+n%k)%k（結(jié)合率） (m*n)%k=((m%k)*n)%k （交換率） 則 x%m = (x1 + x2*10 + x3*102 +xn*10n-1)%m = (x1%m+ x2*10%m+ x3*102%m +xn*10n-1%m)%m = (x1%m+ (10%m*x2)%m + (102%m*x3)%m +(10n-1%m*xn)%m)%m = (x1 + 10%m*x2+ 102%m*x3 +10n-1%m*xn)%m 所以公式得證 舉例： 如果一個(gè)數(shù)的所有數(shù)字之和能被3整除，則這個(gè)數(shù)能被3整除 10%3=1,100%3=1,1000%3=1.....10n%3=1 x%3=(x1 + x2+ x3 +......+xn)%3 如果一個(gè)數(shù)的個(gè)位數(shù)能被5整除，則這個(gè)數(shù)能被5整除，也就是說個(gè)位為0或5的數(shù)都能被 5整除10%5=0,100%5=0,1000%5=0.....10n%5=0 x%5=x1%5 對(duì)于7這個(gè)數(shù)比較麻煩，用語言不好直接描述了，大家看公式就知道了 10 %7=3,102%7=2,103%7=6,104%7=4,105%7=5,106%7=1, 107%7=3,108%7=2..... x%7=(x1 + 3x2+ 2x3+ 6x4+ 4x5+ 5x6+ x7+......)%7 也可寫為 x%7= (x1 + 3x2+ 2x3 - x4 - 3x5 - 2x6+ x7+......)%7 例： 567%7=(7+3*6+2*5)%7=(7+18+10)%7=35%7=0 所以567%7=0

題目位置

[碼題集](碼蹄集 (matiji.net))

思想迸發(fā)

首先就是判斷每一個(gè)數(shù)的 各個(gè)位數(shù)之和 % 3 == 0 話 cnt++ 否則將 !=0 放入數(shù)組index 將index[i] + index[i+1] %3 ？= 0 √ cnt++ 同時(shí)將index[i] = index[i+1] = -1 最后cnt /= 2 因?yàn)閮蓚€(gè)數(shù)字為一組啊啊啊

AC code

#include<bits/stdc++.h>using namespace std; typedef long long ll; #define quicken ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define MAX_NUM 10005 #define MOD 100000007 #define PI 3.1415926double res; ll ans, n, m, t, k,len, cnt = 0, minn = MAX_NUM,maxx = 0; char ch, s1[MAX_NUM] = "", s2[MAX_NUM] = ""; bool flag = false;ll get_sum(ll t) {ll temp = 0;while (t) {temp += t % 10;t /= 10;}return temp; }int main() {quicken;ll index_num = 0;cin >> n;vector<ll> index;for(int i = 1; i <= n; i++) {cin >> index_num;if(get_sum(index_num) % 3 == 0) {cnt++;} else {// push_back就是將值放入vector的最后一位，其實(shí)是每次放入都進(jìn)行一次malloc重新分配內(nèi)存index.push_back(get_sum(index_num));}}for(int i = 0; i < index.size(); i++) {if(index[i] == -1) continue;for(int j = i+1; j < index.size(); j++) {if(index[j] == -1) continue;if((index[i] + index[j]) % 3 == 0) {cnt += 2;index[i] = -1;index[j] = -1;break;}}}cnt /= 2;cout << cnt << endl;return 0; } //3 //123 123 99

下面是一些無聊的東西哈哈哈!!!.

淺紅色文字：淺紅色文字：

深紅色文字：深紅色文字

淺綠色文字：淺綠色文字

深綠色文字：深綠色文字

淺藍(lán)色文字：淺藍(lán)色文字

深藍(lán)色文字：深藍(lán)色文字

淺黃色文字：淺黃色文字

深黃色文字：深黃色文字

淺青色文字：淺青色文字

深青色文字：深青色文字

淺紫色文字：淺紫色文字

深紫色文字：深紫色文字

總結(jié)

以上是生活随笔為你收集整理的MT2007-快速判断一个数能否被整除的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。