周赛Problem 1021: 分蛋糕（埃拉托斯特尼筛法）

Problem 1021: 分蛋糕

Time Limits: 1000 MS Memory Limits: 65536 KB

64-bit interger IO format: %lld Java class name: Main

Description

今天欧文出新品，筱丽学姐请实验室大家吃蛋糕体积为m,mm,m为整数，她将蛋糕平分成了mm块，每块体积为11,但她要求每个人吃nknk块，每种情况下nn相同,且相同的kk的个数小于nn,n≠1,k≠0n≠1,k≠0，即可以从mm中挑出几块组成nknk；每个人吃的块数可以相同,如果不能恰好吃完，那她将独吞所有蛋糕；问共有几种分法能让大家吃到蛋糕；

Input

蛋糕的体积m,2≤m≤1012m,2≤m≤1012；

Output

有几种分法

Sample Input

6

2

Output for Sample Input

3

1

Hint

m=6, 共三种 {21,22},{31,31},{61};

经过同学和学姐的指点才做出来。

思路：题意情况下方案数可以先将输入的n分解为素数乘积的形式，然后将每一位的指数+1，然后累乘指数得到r，答案就是r-1。

代码：

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#define INF 0x3f3f3f3f

#define MM(x) memset(x,0,sizeof(x))

using namespace std;

typedef long long LL;

void finder(LL n)

{

    LL a=2,i=0,r=1;

    while(a*a<=n)

    {

    	i=0;

        while(n%a==0)

        {

            n=n/a;

            i++;

        }

        r=r*(i+1);

        a++;

    }

    if(n>1)

		r*=2;

    printf("%lld\n",r-1);

}

int main(void)

{

	LL n;

	while (~scanf("%lld",&n))

	{

		finder(n);

	}

	return 0;

}

秒客网