牛客nc54841 3的倍数-爱代码爱编程

题目链接 https://ac.nowcoder.com/acm/problem/54841
题目求从l到r的数将其拼接起来，问是否为3的倍数。
一般做法

第一次的想法是将每一个数的位数给他相加，如果可以被3整除就代表他是
3的倍数，但是超时了，因为很容易可以想到，我们的数据可能是1-1^18而我们这种写法的时间复杂度是O(n*m),想一下，极端情况肯定是超出的

#include<bits/stdc++.h>

using namespace std;
const int N = 100;
typedef long long ll;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		ll l, r;
		cin >> l >> r;
		ll ans = 0;
		for (ll i = l; i <= r; i++)
		{
			ll c = i;
			while (c)
			{
				ans += c % 10;
				c /= 10;
			}
		}
		if (ans % 3 == 0)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
	return 0;
}

我们找一找规律可以发现，我们所有的数中没过三个数就一定有一个数可以被三整除，然后我们其他的两个数的对三的余数相加又一定是3，所以我们可以换一种思路，我们直接去判断第一个数和最后一个数的余数情况，并以此来判断是否可以被三整除，具体看注释
AC做法

	#include<bits/stdc++.h>

using namespace std;
const int N = 100;
typedef long long ll;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		ll l, r;
		cin >> l >> r;
		//我们全看第一个数和最后一个数对于3的余数
		ll res = l % 3;
		ll ans = r % 3;
		//第一个数被三整除，那么如果最后一个数余2，那么肯定中间又一个1，
		//那么肯定1+2为3，或者为0，直接过
		if (res == 0 && (ans == 2 || ans == 0))
		{
			cout << "YES" << endl;
		}
		//同样的，我们可以发现余1的情况
		else if (res == 1 && (ans == 2 || ans == 0))
		{
			cout << "YES" << endl;
		}
		//同上，可以多写几个数来观察
		else if (res == 2 && ans == 1)
		{
			cout << "YES" << endl;
		}
		//除了这些，其他情况都不行
		else
		{
			cout << "NO" << endl;
		}
	}
	return 0;
}