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;
}
时间: 07-09

NOIP模拟:切蛋糕(数学欧拉函数)的相关文章

【学习总结】数学-欧拉函数

定义 欧拉函数f(n)表示小于n并且与n互质的数的个数 f(n)=n(1?1p1)(1?1p2)-(1?1pk)(pi为n的质因子) 代码 C++ 单个处理 int eulerPhi(int n) { int m = (int)sqrt(n+0.5); in ans = n; for (int i = 2; i <= m; i++) { if (n % i == 0) { ans = ans / i * (i-1); while (n%i==0) n /= i; } } if (n > 1)

【BZOJ4173】数学 欧拉函数神题

[BZOJ4173]数学 Description Input 输入文件的第一行输入两个正整数 . Output 如题 Sample Input 5 6 Sample Output 240 HINT N,M<=10^15 题解:STEP 1: 这步还是很容易的吧~毕竟原来的式子不太舒服.但是注意,最后一个式子的取值只能为0或1,所以就变成了. STEP 2: 这步倒是难理解一些,但是考虑:我们将这三个等式都算出来,如果满足了左边那个条件,那么这三个等式加起来为1,对答案的贡献正好为$\varphi

【BZOJ-4173】数学 欧拉函数 + 关于余数的变换

4173: 数学 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 306  Solved: 163[Submit][Status][Discuss] Description Input 输入文件的第一行输入两个正整数 . Output 如题 Sample Input 5 6 Sample Output 240 HINT N,M<=10^15 Source Solution 数论好题,开始无从下手,推导后感觉新姿势++ 题目大意:求$\varphi(

LA 7362 Farey (数学,欧拉函数)

题意:给定一个数 n,问你0<= a <=n, 0 <= b <= n,有多少个不同的最简分数. 析:这是一个欧拉函数题,由于当时背不过模板,又不让看书,我就暴力了一下,竟然AC了,才2s,题目是给了3s,很明显是由前面递推,前面成立的,后面的也成立, 只要判定第 i 个有几个,再加前 i-1 个就好,第 i 个就是判断与第 i 个互质的数有多少,这就是欧拉函数了. 代码如下: 这是欧拉函数的. #pragma comment(linker, "/STACK:102400

UVA 11426 - GCD - Extreme (II) 欧拉函数-数学

Given the value of N, you will have to ?nd the value of G. The de?nition of G is given below:G =i<N∑i=1j∑≤Nj=i+1GCD(i, j)Here GCD(i, j) means the greatest common divisor of integer i and integer j.For those who have trouble understanding summation no

数学之欧拉函数 &amp;几道poj欧拉题

欧拉函数总结+证明 欧拉函数总结2 POJ 1284 原根 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int Euler(int n) { int res=n; for(int i=2;i*i<=n;i++) { while(n%i==0) { n/=i; res

O(N)的素数筛选法和欧拉函数

首先,在谈到素数筛选法时,先涉及几个小知识点. 1.一个数是否为质数的判定. 质数,只有1和其本身才是其约数,所以我们判定一个数是否为质数,只需要判定2~(N - 1)中是否存在其约数即可,此种方法的时间复杂度为O(N),随着N的增加,效率依然很慢.这里有个O()的方法:对于一个合数,其必用一个约数(除1外)小于等于其平方根(可用反证法证明),所以我们只需要判断2-之间的数即可. bool is_prime(int num) { const int border = sqrt(num); for

Password (欧拉函数降幂)

Password 时间限制: 1 Sec  内存限制: 64 MB提交: 55  解决: 35[提交][状态][讨论版] 题目描述 Rivest是密码学专家.近日他正在研究一种数列E = {E[1],E[2],--,E[n]}, 且E[1] = E[2] = p(p为一个质数),E[i] = E[i-2]*E[i-1] (若2<i<=n). 例如{2,2,4,8,32,256,8192,--}就是p = 2的数列.在此基础上他又设计了一种加密算法,该算法可以通过一个密钥q (q < p)

POJ2480 Longge&#39;s problem 欧拉函数的应用 &amp;&amp; 积性函数

题意很简单,求sum(gcd(i,n))   1<=i<=n; 这题看到后第一反应并没有里用积性函数的性质,不过也可以做,欣慰的是我反应还是比较快的 设f(n)=gcd(1,n)+gcd(2,n)+....+gcd(n-1,n) + gcd(n,n), 用g(n,i)表示满足 gcd(x,n)=i的 x的个数 (x小于n),则 f(n)=sum{i*g(n,i)}; 同时又利用 扩展欧几里德的性质  gcd(x,n)=i  的充要条件是 gcd(x/i,n/i)==1,所以 满足 x/i的解有