UOJ Logo

NOI.AC

1S 512MB
Statistics

题目描述

定义一个二元组 $(i,j)$ 是好的,当且仅当 $i$ 和 $j$ 均为整数且其二进制和三进制表示在相加时都不进位。

给定 $n$,求满足 $1\le i,j\le n$ 的二元组 $(i,j)$ 中好二元组的数量。

输入格式

一行共一个整数 $n$。

输出格式

一行共一个数 $m$,表示满足要求的好二元组数量。

样例输入 #1

4

样例输出 #1

4

样例解释 #1

满足条件的二元组为 $(1,4)$,$(3,4)$,$(4,1)$ 和 $(4,3)$。下举两例作为参考,其余同理可得。

对于 $(1,2)$,

$$1+2=3$$ $$1=(1)_2,2=(10)_2,3=(11)_2$$ $$1=(1)_3,2=(2)_3,3=(10)_3$$

易知其在二进制下符合要求,三进制下不符合要求。故 $(1,2)$ 不是好的二元组。

对于 $(3,4)$,

$$3+4=7$$ $$3=(11)_2,4=(100)_2,7=(111)_2$$ $$3=(10)_3,4=(11)_3,7=(21)_3$$

易知其在二进制和三进制下均符合要求。故 $(3,4)$ 是好的二元组。

样例输入 #2

10

样例输出 #2

16

数据规模与约定

本题目采用 $\text{subtask}$ 测试

对于 $100\%$ 的数据,$1\le n\le 5000$。

具体数据范围如下:

$\text{subtask 1(10pts)}$:$1\le n\le 10$;

$\text{subtask 2(20pts)}$:$1\le n\le 100$;

$\text{subtask 3(20pts)}$:$1\le n\le 1000$​;

$\text{subtask 4(50pts)}$:无特殊限制。