【NOIP训练】【规律+数论】欧拉函数的应用

时间:2022-06-28 09:15:06

Problem 1

【题目大意】

给出 【NOIP训练】【规律+数论】欧拉函数的应用

多组数据 【NOIP训练】【规律+数论】欧拉函数的应用,给出  【NOIP训练】【规律+数论】欧拉函数的应用 求出 【NOIP训练】【规律+数论】欧拉函数的应用

题解

【NOIP训练】【规律+数论】欧拉函数的应用

证明:  【NOIP训练】【规律+数论】欧拉函数的应用 除了 【NOIP训练】【规律+数论】欧拉函数的应用 以为均为偶数, 所以互质的个数成对。

【NOIP训练】【规律+数论】欧拉函数的应用【NOIP训练】【规律+数论】欧拉函数的应用

所以对于每对的和为 【NOIP训练】【规律+数论】欧拉函数的应用 , 共有 【NOIP训练】【规律+数论】欧拉函数的应用 对 。

【NOIP训练】【规律+数论】欧拉函数的应用

Problem 2

【题目大意】

在第一个圆上写入  【NOIP训练】【规律+数论】欧拉函数的应用 ,在第二个圆上写入【NOIP训练】【规律+数论】欧拉函数的应用 ,此后每一次在前一个圆的基础上,每两个数之间写上他们的和,定义 【NOIP训练】【规律+数论】欧拉函数的应用 为第i个圆中数字i的个数。

【NOIP训练】【规律+数论】欧拉函数的应用

给出 【NOIP训练】【规律+数论】欧拉函数的应用 ,求 【NOIP训练】【规律+数论】欧拉函数的应用

题解

【NOIP训练】【规律+数论】欧拉函数的应用

证明:【NOIP训练】【规律+数论】欧拉函数的应用【NOIP训练】【规律+数论】欧拉函数的应用,圆中的数字相邻两两互质。

对于一个数字 【NOIP训练】【规律+数论】欧拉函数的应用 只可能由与他互质的两个数 【NOIP训练】【规律+数论】欧拉函数的应用 相加而成并且每一种构造方法是唯一的。

所以 【NOIP训练】【规律+数论】欧拉函数的应用