首页 > 代码库 > 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模拟:切蛋糕(数学欧拉函数)