Skip to content

11543: 【原1543】mod3

题目

题目描述

author: yzh119 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1543

Description

求\({n\choose k}(0\leq k \leq n)\)中三的倍数的个数。

Input Format

共一行,包含一个整数\(n\)。

Output Format

共一行,包含一个整数表示答案。

Sample Input 1

3

Sample Output 1

2

Sample Input 2

10

Sample Output 2

7

Limits

对于50%的数据,\(n < 1000\)。

对于100%的数据,\(n < 2^{63}\)。

yyong119's solution

#include <iostream>
using namespace std;
long long n;
long long num(long long x) {
    if (x < 3) return x;
    long long r = x / 3, m = x - r - (r << 1);
    return (m + 1) * num(r) + m;
}
int main() {
    cin >> n;
    cout << n - num(n);
    return 0;
}