首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。