SGU105

2019-04-13 16:18发布

站内文章 / 模拟电子
10164 0 1583
题目大意 定义一个数列 1,12,123,1234,12345......12345678910,1234567891011 求第1-n项中能整除3的项的项数

没的说，跟HNOI2011 day1 T1太像了……虽然完全不是一个做法…… HNOI那题是要求第n项模某一个数的余数，可矩乘解决
观察数列可得，第i项模3的余数为 第i-1项模3的余数+i 模3 再进一步观察 第二项，第三项满足要求 那么ans=n/3*2 如果n mod 3==2 ans++ 代码实际上就两行…… //Lib #include #include #include #include #include #include #include #include #include #include using namespace std; //Macro #define rep(i,a,b) for(int i=a,tt=b;i<=tt;++i) #define rrep(i,a,b) for(int i=a,tt=b;i>=tt;-- #define erep(i,e,x) for(int i=x;i;i=e[i].next) #define irep(i,x) for(__typedef(x.begin()) i=x.begin();i!=x.end();i++) #define read() (strtol(ipos,&ipos,10)) #define sqr(x) ((x)*(x)) #define pb push_back #define PS system("pause"); typedef long long ll; typedef pair pii; const int oo=~0U>>1; const double inf=1e20; const double eps=1e-6; string name="",in=".in",out=".out"; //Var int n; void Work() { scanf("%d",&n); printf("%d ",n/3*2+(n%3==2)); } int main() { // freopen((name+in).c_str(),"r",stdin); // freopen((name+out).c_str(),"w",stdout); // Init(); Work(); return 0; }

热门文章