首页 > 试题广场 >

被3整除

[编程题]被3整除
  • 热度指数:138973 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

小Q得到一个神奇的数列: 1, 12, 123,...12345678910,1234567891011...。

并且小Q对于能否被3整除这个性质很感兴趣。

小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。


输入描述:
输入包括两个整数l和r(1 <= l <= r <= 1e9), 表示要求解的区间两端。


输出描述:
输出一个整数, 表示区间内能被3整除的数字个数。
示例1

输入

2 5

输出

3

说明

12, 123, 1234, 12345...
其中12, 123, 12345能被3整除。
写出来当插入i以后的规律:
i = 1 ----> 1
i = 2 ----> 0
i = 3 ----> 0
i = 4 ----> 1
i = 5 ----> 0
i = 6 ----> 0
i = 7 ----> 1
………………
发现在区间[1,x]之间共计有 ***(x) = (x+2)/3 个1,剩下的都满足要求
那么在区间[l, r]上的 r-l+1个 数字中,必须抠掉 ***(r) - ***(l-1) 个不满足要求的数字。
直接打印出来就可以了,O(1),不需要循环遍历。
#include<stdio.h>
#define ***(x) (((x)+2)/3)
int main(){
    int l, r;
    while(~scanf("%d%d", &l, &r))
        printf("%d\n", r-l+1-***(r)+***(l-1));
    return 0;
}
============补充证明=============
记插入数字i以后形成的新数字为a[i],数字a[i]的余数记作last[i]
容易发现,a[i] = a[i-1]*10k + i
last[i] = a[i]%3 = (a[i-1]*10+ i)%3 
= (a[i-1]*(10-1) + (a[i-1] + i))%3
=(a[i-1] + i)%3
=(a[i-1]%3 + i%3)%3
=(last[i-1] + i%3)%3

则last满足递推关系:
  • last[i] = (last[i-1] + i%3)%3
数学归纳法:
当k = 0的时候:
last[0] = 0、last[1] = 1、last[2] = 0成立

假设规律last[3k+1] = 1、last[3k] = 0、last[3k+2] = 0成立;
则对于任意k+1而言
last[3(k+1)] = last[(3k+2) + 1] = (0 + 3(k+1)%3)%3 = 0
last[3(k+1)+1] = (0 + (3(k+1)+1)%3)%3 = 1
last[3(k+1)+2] = (1 + (3(k+1)+2)%3)%3 = (1+2)%3 = 0
可见对任意k,上述规律恒成立。

综上,last[i] = i%3==1
编辑于 2018-03-28 17:28:44 回复(33)
一个数所有位数的和相加如果等于3的倍数,则这个整数是3的倍数。 这里第一个数是1,第二个是12,第三个是123……第n个数是123……(n-1)n,各个位之和可以算成(i+1)*i/2,这里如果是大于等于两位数,它算成一个数和把每一位分开计算对3取余的结果都是一样的,所以没关系。 所以,直接遍历l到r,根据通项公式判断即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main(){
    ll l , r;
    while(cin >> l >> r){
        ll count = 0;
        for(int i = l; i <= r; i++){
            if((i+1)*i/2 % 3 == 0)    count++;
        }
        cout << count << endl;
    }
    return 0;
} 

编辑于 2018-03-28 22:26:41 回复(24)
#include<iostream>
using namespace std;

int main(){
    int left, right;
    int result = 0;
    
    cin >> left >> right;
    for(int i=left; i<=right; ++i){
        switch(i%3){
            case 1: ;break;
            case 2: ++result;break;
            case 0: ++result;break;
        }
    }
    cout << result << endl;
}

编辑于 2018-03-28 17:37:13 回复(11)
#include <iostream>
using namespace std;

int main(void){
    int i, j;
    int count = 0;
    cin>>i>>j;
    for(int k = i; k <= j; k++){
        if(k % 3 != 1)
            count++;
    }
    cout<<count;
    return 0;
}
能被3整除的数的特征:各个数位上数字之和能被3整除
推广:不是一个数字一个数字地拆分,把某个数视为字符串划分为多个任意长度的数字字符串,比如a=137928672拆成b=137,c=9286,d=72,那么有a%3=(b+c+d)%3
题中数组A第i个数A[i]是从1写到i的数,根据推广的结论把它拆成1,2,3,4,5,...,i,则有:
A[i]%3=(1+2+3+...+i)%3
而自然数序列1,2,3,4,5...i取模3的结果分别是1,2,0,1,2,0,...,i%3,也就是:
A[i]%3=(1+2+0+1+2+0+...+i%3)%3
因为1+2=3刚好能被3整除,当i%3=0时,右边括号内是1,2,0的重复序列,当然能被3整除,当i%3=2时,右边括号内是1,2,0重复序列最后跟上1,2,末尾没有0但还是能被3整除,当i%3=1时,显然A[i]%3=1
综上所述:i%3=0或2时A[i]能被3整除,否则A[i]%3=1
—————————更新———————————
同样的代码,一会通过,一会又不通过,练习模式下看失败时的输入用例是空的,这得要牛客背锅
编辑于 2019-09-02 20:54:24 回复(5)
public class T2 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int count = 0;
        for(int i=n;i<=m;i++){
            if(i%3%2==0){
                count++;
            }
        }
        System.out.println(count);

    }

}
发表于 2018-04-14 13:06:42 回复(16)
龟头像
import sys
a = sys.stdin.readline().strip().split()
ans = 0

i = int(a[0])
j = int(a[1])

total1 = (1 + i)*i//2
total2 = (2 + i)*(i+1)//2
total3 = (3 + i)*(i+2)//2
mod = [total1%3, total2%3, total3%3]

ans += 2*((j-i+1)//3)
ansmod = (j-i+1)%3

ans += mod[:ansmod].count(0)

print(ans)


发表于 2018-03-28 10:38:50 回复(4)
发现:第i个数为123...i, 则第L个数为123...L,能被3整除的数有一个性质,即各个位加和能
被3整除,例如:若第L个数能被3整除即: 123...L能被3整除则(1+2+3+ ...+L)能被3整除
import java.util.*;

public class Main {
public static void main(String[] args){
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int l = input.nextInt();
int r = input.nextInt();
long sum = 0;
for(int i = 1; i < l; i++){
sum += i;
}
int count = 0;
for(int i = l; i <= r; i++){
sum += i;
if(sum % 3 == 0)
count++;
}
System.out.println(count);
}
input.close();
}
}

编辑于 2019-08-01 09:21:41 回复(9)
#include<stdio.h>
int main()
{
    int l,r,i,j;
    while(~scanf("%d %d",&l,&r))
    {
        i=(r-l)/3;
        j=(r-l)%3;
        if(j==0)
            j=i;
        else
            j=i+j;
        printf("%d\n",j);
    }
}
自己列举可以发现规律,给定一个数X,X/3即为1——X的能被3整除的个数,但是这是在默认1起步的情况下。当起始点发生变化,我们就需要考虑到余数。假定(L-R)/3为正确的个数,事实并非如此,通过找规律可发现(L-R)%3一直在0,1,2之间连续变动,且为1,2时正解应该为(L-R)/3+1。
发表于 2020-04-23 11:40:54 回复(0)
好多人抖机灵,我来说一下常规思路。
1),首先确定第n个数的合成规律为1·2·····n(表示连接),结合小学学过的被3整除的数的规律,判定第n个数的方法就是判定sum(1)+......+sum(n)被3整除,其中sum(n)表示数字n每一位之和。
2),做到第一步是不够的,因为时间复杂度太高,光判定一个数复杂度就是o(n)了,必须降到o(1)。观察发现,这是一个正整数数列1,2......n,并考察每个数的被3整除性(只考虑每个正整数除3的余数)时发现,余数要么是1,要么是2,要么是0,也就是3个一次循环,而且还是周期性的,这个很好理解。如果数列恰好是若干个循环,那么其和一定是3的倍数;如果数列恰好是若干个循环多了一个1,那么一定不是3的倍数;如果数列恰好是若干个循环多了1和2,那么一定是3的倍数。也就是说要看n%3,如果不是1,则sum(1)+......+sum(n)是3的倍数,即第n个数是3的倍数。
3),再次加速。发现l到r也是正整数序列,判定的也是被3整除性,照第二步的葫芦画瓢,整体时间复杂度可以降低为o(1)

#include<stdio.h>
#define func(x) (((x)/3)*2+(((x)%3==2)?1:0)) /*func(x)表示正整数1~x中除3余数不为1的数的个数*/
int main()
{
    int l,r;
    while(~scanf("%d %d",&l,&r))
    {
        printf("%d\n",func(r)-func(l-1));
    }
}
以上代码,运行时间为2ms

编辑于 2019-10-05 00:22:02 回复(0)
Java版解法:佛系了,提交四次,成功三次。思路主要是找规律,从1到10,除了1,4,7,10这几位加在后面除3余数为1的数不能被3整除外其他都能。(PS:我总觉得这题有些问题,不知道是系统的原因还是什么,有时候能成功有时候失败,一开始以为是l,r都是大数,需要先用String,后来一直报错【返回非零】,抱着试试的想法重写了这个简单的,结果突然成功了。有大佬有更好的写法么,欢迎交流。)
import java.util.Scanner;

public class Main  {
    public static int sum(int i){
        return i/3*2+(i%3==2?1:0);
    }
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int l = input.nextInt();
        int r = input.nextInt();
        System.out.println(sum(r) - sum(l-1));
    }
}

发表于 2019-08-04 19:18:06 回复(3)

```思路常规比较容易想到 没有高赞的精妙

#include<iostream>

#include<vector>
using namespace std;
int main()
{
int a,b,cnt=0;
long long sum=0;
while(cin>>a>>b)
{
if(a>b) return -1;
for(int i=1;i<=a;i++)
sum+=i;
for(int i=a+1;i<=b+1;sum+=i,i++)
if(sum%3==0) cnt++;
}
cout<<cnt<<endl;
return 0;
}```

编辑于 2019-07-07 15:55:00 回复(0)
"""
从l到n遍历:
可以被3整除的数  加上 余1的数  余1
余1的数         加上 余2的数  可以被3整除
可以被3整除的数 加上 余0的数  也可以被3整除
3个为一组,后两个可以被整除
"""


def cnt_mod_3(n):
    return (n // 3) * 2 + max(0, n % 3 - 1)


if __name__ == "__main__":
    l, r = list(map(int, input().strip().split()))
    print(cnt_mod_3(r) - cnt_mod_3(l - 1))

编辑于 2019-07-16 12:14:58 回复(3)
import sys
l,r=map(int,sys.stdin.readline().split())
def getnum(integer):
    if integer-integer//3*3==2:
        s=1
    else:
        s=0
    return integer//3*2+s
print(getnum(r)-getnum(l-1))

发表于 2019-08-05 10:31:01 回复(1)

本套8道题全部pass的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)
牛客网上的其他题目解答也在持续更新。

#include <iostream>
using namespace std;
int main()
{
    int l, r; cin >> l >> r;
    int count = (r - l + 1) / 3 * 2;
    int num = r - l + 1 - (r - l + 1) / 3 * 3;
    if (num == 1 && (l % 3 == 0 || l % 3 == 2)) {
        count += 1;
    }
    else if (num == 2 && (l % 3 == 0 || l % 3 == 1)) {
        count += 1;
    }
    else if (num == 2 && l % 3 == 2) {
        count += 2;
    }
    cout << count;
    return 0;
}
发表于 2018-03-28 19:12:48 回复(0)
这里可以用到一个数学课学过的性质。如果a+b+c的值可以被3整除。那么abc组成的数也能够被3整除。
#include<iostream>
using namespace std; 
typedef long long ll; 

ll getSum(ll num){
    ll tmp = 0;
    for(ll i=1; i<=num; i++){
        tmp += i;
    }
    return tmp; 
}

int main(){
    ll l,r;
    while(cin >> l >> r){
        ll cnt = 0;
        ll tmp = getSum(l);
        for(ll i=l; i<=r; i++){
            if(tmp % 3==0) cnt++;
            tmp += i+1;
        }
        cout << cnt <<endl;
    }
}

发表于 2018-03-27 23:22:38 回复(10)
每三个数中有两个能被3整除,所以我们可以把数字按成多份,每份有3个,每3个中有2个能被3整除。就是i=n/3*2这个式子。分完之后,再对多余部分进行分析,若余数为0,则直接输出;若不为0,则多出的数只可能是1个或2个,这时我们求出第一个数的规律位置j=l%3
如果j=0,则第一个数能被3整除,且下一个数不能被3整除,得i += 1;
如果j=1,则第一个数不能被3整除,且下一个数能被3整除,得i += j-1;
如果j=2,则第一个数能被3整除,且下一个数也能被3整除,得i += j;

using System;

namespace 被3整除
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(1 / 3);
string str = Console.ReadLine();
int l = int.Parse(str.Split(" ")[0]);
int r = int.Parse(str.Split(" ")[1]);
int i = (r - l + 1) / 3 * 2;
int j = (r - l + 1) % 3;
if (j == 0) Console.Write(i);
else
{
if (l % 3 == 0) Console.Write(i + 1);
else if (l % 3 == 2) Console.Write(i + j);
else Console.Write(i + j - 1);
}
}
}
}


编辑于 2020-04-23 01:14:39 回复(1)
# 受到 lslotus 找规律的启发,写出了下面的程序
import sys
import sys
a = sys.stdin.readline().strip().split()
l, r = map(int, a)

def solution(l, r):
    ans = (r - l + 1) // 3 * 2
    for i in range(l, l + (r - l + 1) % 3):
        if i % 3 == 1:
            continue
        else:
            ans += 1
    return ans

if __name__ == '__main__':
    print(solution(l, r))
时间复杂度为 O(1)
发表于 2020-04-15 15:11:04 回复(0)
#include <stdio.h>
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int cnt1,cnt2;
    cnt1=(m/3)*2;
    if(m%3==2) cnt1++;
    cnt2=(n/3)*2;
    if(n%3==0) cnt2--;
    printf("%d\n",cnt1-cnt2);
}

发表于 2020-04-11 12:08:49 回复(0)
if( ( i % 3 )% 2 == 0) count ++;
我来解释下为什么用序号%3%2就可以判断。
如i=8时,即12345678,各位数的和是1+2+3+4+5+6+7+8
请注意,连加中出现的3的倍数是不会影响结果的,无论和是否能被3整除,再加一个3的倍数都不会改变.因此,我们可以把连加式子化简:将3的倍数剔除。
1+2+4+5+7+8
接下来,你会发现,连续出现的两个数相加一定是3的倍数,因此也可以相互约去。
[(1+2)+(4+5)+(7+8)] % 3 = 0
因此,去掉3的倍数后有偶数个数字时,它们的和一定可以被3整除!奇数个时一定不可以被3整除!
可能有的人会问:碰到进位情况时,两个不能被3整除的连续的数字相加不一定为3的倍数,但实际上是的。因为每次进位都会减去若干个9,再加一。
如199 进位到 200 , 此时要减去2个9,再加1 , 减去9不影响,再加一,等于不进位时加一。

编辑于 2020-04-06 19:59:02 回复(0)

热门推荐

通过挑战的用户

查看代码