首页 > 代码库 > NOIP模拟:切蛋糕(数学欧拉函数)
NOIP模拟:切蛋糕(数学欧拉函数)
题目描述
BG 有一块细长的蛋糕，长度为 n。
有一些人要来 BG 家里吃蛋糕， BG 把蛋糕切成了若干块(整数长度)，然后分给这些人。
为了公平，每个人得到的蛋糕长度和必须相等，且必须是连续的一段。
但是， BG 并不知道要有多少人来。 他只知道， 来的人数为n的约数，且小于n。
显然把蛋糕平均分成 n 块一定能满足要求。但是， BG 想要分出的块数尽量少。现在 BG
想知道，他要把蛋糕分成至少多少块，才能使得不管多少人来都能满足要求。
输入格式
输入文件名为 cake.in。
输入共一个整数 n，表示蛋糕的长度。
输出格式
输出文件名为 cake.out。
输出共一个整数， 表示分出的最少块数。
样例输入1
6
样例输出1
4
样例输入2
15
样例输出2
7
题目分析
拿15的分割为例子：
可以看出切割处均为15的约数(在15处会出现重叠)，
若设 f(x) 表示15中x的倍数有几个，则答案应为
$$ans = f(3) + f(5) - f(15) $$
其实就是n - 小于n且与n互质的数---->欧拉函数
欧拉函数$\phi$(n) ： $\phi$(n) 表示[1, n]中与 n 互质的整数的个数。
主要公式: $$phi(n) = n · prod_{p \in P} \frac{p - 1}{p}$$
欧拉函数有两种求法：
- 多个数的欧拉函数
void sieve() { phi[1] = 1; for (int i = 2; i < N; ++i) { if (!pr[i]) prime[pn++] = pr[i] = i, phi[i] = i - 1; for (int j = 0; j < pn; ++j) { int k = i * prime[j]; if (k >= N) break; pr[k] = prime[j]; if (i % prime[j] == 0) { phi[k] = phi[i] * prime[j]; break; } else phi[k] = phi[i] * (prime[j] - 1); } }}
- 求一个数的欧拉函数
p = ans = n; for(int i = 2; i * i <= p; i++){ if(p % i == 0) ans = ans / i * (i - 1) ; while(p % i == 0) p /= i; } if(p != 1) ans = ans / p *(p - 1) ;
本题只需求一个值。
CODE
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<algorithm>using namespace std;int phi;int ans;int n, p;int main(){ cin>>n; p = ans = n; for(int i = 2; i * i <= p; i++){ if(p % i == 0) ans = ans / i * (i - 1) ; while(p % i == 0) p /= i; } if(p != 1) ans = ans / p *(p - 1) ; cout<<n - ans; return 0;}
NOIP模拟:切蛋糕(数学欧拉函数)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。