游客 注册 | 登录
中文 | En

3535 - 切蛋糕

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

你有一块非常长且薄的蛋糕。我们可以认为它是一维的，长度为n。
今天是你的生日，你有不少朋友要来你的寝室开party。
在你朋友到来前，你想要把蛋糕切好成若干块。

当你的朋友到来时，你会用以下规则来分配蛋糕。
从蛋糕的左端开始，你给你的第一位朋友若干块连续的蛋糕，接下来你给第二位朋友之后的若干块连续的蛋糕，以此类推。

你显然被朋友认为是一个非常nice的人，也就是你必须保证每个人分到的蛋糕量是相同的。
不同的朋友拿到的蛋糕块数可能不同，但量必须相同。

你已经不记得你邀请了多少位朋友，但你非常清楚地记得，朋友的个数x是一个蛋糕长度n的因子，且x<n。

现在，你要开始切蛋糕了，你必须保证，对于任何可能的朋友个数x，按照以上的蛋糕分配法则，都是可以做到每个人拿到的蛋糕量相同。

请计算，你最少需要把蛋糕切成多少块，来达到以上要求。

<br />


下面解释第一组样例数据。

由于蛋糕长度为6。所以朋友个数x可能为1个，2个或者3个。
我们可以将蛋糕切成2,1,1,2，这样的4份。
如果只有1个朋友，直接全部给他。
如果有2个朋友，我们将第一块和第二块给第一个朋友，第三块和第四块给第二个朋友。
如果有3个朋友，我们将第一块给第一个朋友，第二和第三块给第二个朋友，第四块给第三个朋友。
以上的切法是最少的。
所以答案为4。

题目输入

多组输入数据
每组数据第一个数为n

表示蛋糕的长度(2&lt;=n&lt;=123456)


<br />

题目输出

对于每组数据，输出你最少需要把蛋糕切成多少块。

输入/输出样例

输入格式

6
3
15

输出格式

4
1
7

C++解答

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cassert>
#include <complex>
#include <ctime>

#define clr(x,a) memset(x,a,sizeof(x))
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define repeat(i, a, b) for(int i=(a);i<=(b);i++)
#define all(v) (v).begin(), (v).end()
#define Unique(store) store.resize(unique(store.begin(),store.end())-store.begin())
#define X first
#define Y second



using namespace std;
const int N=123456+10;
bool cnt[N];
int cut(int n) {
    vector<int> div;
    memset(cnt,0,sizeof(cnt));
    for (int i=2; i<n; i++) {
        if (n%i==0) {
            div.push_back(n/i);
        }
    }
    for (int i=0; i<div.size(); i++) {
        int cur=div[i];
        for (int i=cur; i<=n; i+=cur) {
            cnt[i]=true;
        }
    }
    int ret=0;
    for (int i=1; i<=n; i++) {
        ret+=cnt[i];
    }
    return max(ret,1);
}
int main () {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //srand(time(NULL));
    int n;
    while (scanf("%d",&n)!=EOF) {
        cout<<cut(n)<<endl;
    }
    return 0;
}
请先登陆