SGU 105: Div 3

Jasonlin posted @ 2011年3月31日 13:20 in SGU with tags 整除 规律 , 1986 阅读

题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=105

题目大意:

      有一个数列1,12,123,1234,...,12345678910,1234567891011,...,求第N个数前有几个数能被3整除包括N.

解题思路:

      能被3整除的数的特点是各个位上的和加起来能被3整除,看规律可知每3个数中有一个数不能被3整除,那个数就是序数跟3取模是1的那个数。

解题代码:

     

#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
	long long n,t,m;
	while(cin>>n){
		m=n/3*2;
		if(n%3!=0){
			t=n%3-1;
			m+=t;
		}
		cout<<m<<endl;
	}
	return 0;
}

扩展知识:http://en.wikipedia.org/wiki/Divisibility_rule


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter