D. 递归求和

    传统题 1000ms 256MiB

递归求和

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

对于自然数x>10yx,定义对于自然数 x>1 及 0\leq y\leq x, 定义

$$f(x,y)=\left\{ \begin{aligned} & 0 & (y \mid x 且y\neq 1)\\ & f(x,y+1)+1&(y\nmid x 或y=1) \end{aligned} \right. $$

给定自然数N,K,求给定自然数N,K,求 card({x  2xNf(x,0)=K})card(\{x\ |\ 2\leq x\leq N 且 f(x,0)=K\})

符号解释

ab 表示a整除bab的因数,ba的倍数a\mid b\ 表示a整除b,a是b的因数,b是a的倍数

card(A)表示集合A的元素个数card(A)表示集合A的元素个数

输入格式

一行2个正整数N和K。 保证

2N,K2×1092\leq N,K\leq 2\times10^9

输出格式

一个整数代表答案。

输入输出样例 #1

输入 #1

5 2

输出 #1

2

25暑假信奥数学入门组C第九场

未参加
状态
已结束
规则
IOI
题目
5
开始于
2025-8-2 10:00
结束于
2025-8-2 20:00
持续时间
10 小时
主持人
参赛人数
10