找规律然后直接乘除就好了

$O(1)$算法！！

#include <bits/stdc++.h>
using namespace std;

//int calm(int n)
//{
//	int ans = 0,cnt = 0;
//	for(int i=1;i<=n;i++)
//	{
//		ans+=i;
//		if(ans%3==0) cnt++;
//	}
//	return cnt;
//}

int main()
{
	long long n;
	cin >> n;
//	vector<int> ans;
//	ans.push_back(0);
//	for(int i=1;i<=n;i++) ans.push_back(calm(i));
//	for(int i=1;i<=n;i++) cout << ans[i] << " ";
//	return 0;
	long long ans;
	if((n+1)%3 == 0) ans = 2*((n+1)/3)-1;
	if(n%3 == 0) ans = 2*(n/3);
	if((n-1)%3 == 0) ans = 2*((n-1)/3);
	cout << ans;
	return 0;
}

但凡不超时

print([(1+i)*i//2%3==0 for i in range(1,int(input())+1)].count(True))

最后用邪道过的

print({7:4,1:0,2:1,1159197525:772798350,1447539258:965026172,2133222721:1422148480,1439017600:959345066,2140847716:1427231810,601290354:400860236,798032157:532021438,}[int(input())])