首页 > 代码库 > sgu 105 Div 3

sgu 105 Div 3

    一个数能整除3当且仅当各位数之和能整除3。

    有了这个规律就好办了, 但是呢,仔细一看, n太大了, 都到 2^31 了。所以简单的模拟肯定不行。

    这种貌似像数论的题,一时找不到好办法,就打表!

    打表出来是这个样子

    1 0
    2 1
    3 2
    4 2
    5 3
    6 4
    7 4
    8 5
    9 6
    10 6

    很有规律啊,1,22,3,44…… 如果我们把每三个看成一个(不算1),那么就是每三个元素增加2

    于是首先想到是不是 n/3*2 呢? 实验几次发现,不可行,有些不符合,但是我们的思路应该是正确的,仔细一想,由于整除的原因,有精度问题,所以我们先乘后除,可以很大程度上减小这种误差,我直接把表达式换了一下位置 n*2/3就过了。

    代码很简单:

#include <iostream>
using namespace std;
int main()
{
    long long a;
    cin>>a;
    a = a * 2 / 3;
    cout<<a<<endl;
}