您现在的位置是：首页 >其他 >C - 除以 3网站首页其他

有顺序.现在给你两个整数 A 和 B，你必须找到从 A 个数字到 B 个（含）数字的整数个，它们可以被 3 整除。1, 12, 123, 1234, ..., 12345678910, ...

例如，设 A = 3。B = 5。因此，序列中的数字是 123、1234、12345。而 123， 12345 可被 3 整除。因此，结果为 2。

输入

输入以整数 T （≤ 10000） 开头，表示测试用例的数量。

每种情况在一行中包含两个整数 A 和 B（1 ≤ A ≤ B < 2e31）。

输出

对于每个案例，按 Ath 和 Bth 之间的顺序打印案例编号和可被 3 整除的总数。

样本

2
3 5
10 110

Case 1: 2
Case 2: 67

 最简单的想法就是每次+i后判断是否可以%3就可以了,但是 面对A 和 B（1 ≤ A ≤ B < 2e31）的数据量肯定是超时了

#include<bits/std++.h>
using namespace std;
#define int long long 
#define endl '
'
#define JS  ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
int A, B, sum, num, N;
signed main()
{
    scanf("%d",&N);
    for(int j = 1;j <= N;j++)
    {
        sum = num = 0;
        scanf("%d %d",&A,&B);
        num = A * (1 + A) / 2;
        for (int i = A + 1; i <= B; i++)
        {
            if (num % 3 == 0)sum++;
            num += i;
        }
        if (num % 3 == 0)sum++;
        printf("Case %lld: %lld
",j,sum);
    }
    return 0;
}

解决方案?通过预处理一个前缀和数组,对于N个样例进行输出即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int A, B, sum, N;
const int maxn = 2e30;
vector<int>num(maxn);
void Init()
{
    int sum = 0;
    for (int i = 1; i <= maxn; i++)
    {
        sum += i;
        sum % 3 ? num[i] = num[i - 1] : num[i] = num[i - 1] + 1;
    }
}
signed main()
{
    Init();
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        scanf("%d %d", &A, &B);
        printf("Case %lld: %lld
", i, num[B] - num[A - 1]);
    }
    return 0;
}

很好,这样经过测试答案确实也是正确,但是由于是2e31的数据量,数组空间不足,直接段错误了.

那么再换一个新的方案三

又是找规律的时间,不难发现

1 2 3 4 5 6 7 8 9 10

将其%3

1 2 0 1 2 0 1 2 0 1

那么对于n有n / 3 * 2 + (n % 3 == 2)个满足%3的数

为什么是%2 ? 因为每3个数必然有2个满足条件当第4个数出现必然余1打破平衡,而我们的第5个数的余2恰好和1再次满足|3的条件,而第6个数(3的整数倍)必然又是可以被3整除的,依次可以推出以内有多少个满足条件的数

#include <iostream>
using namespace std;
#define int long long
int count(int n)
{
    return n % 3 ? n / 3 * 2 + (n % 3 == 2) : n / 3 * 2;
}

signed main()
{
    int T, A, B;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        cin >> A >> B;
        int ans = count(B) - count(A - 1);
        cout << "Case " << i << ": " << ans << endl;
    }
    return 0;
}