[原创]Light OJ 1014 Ifter Party [因子分解]【数论】

2016-06-29 15:13:15 Tabris_ 阅读数：415

博客爬取于2020-06-14 22:44:19
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51783218

题目链接 ： http://acm.hust.edu.cn/vjudge/contest/view.action?cid=120197#problem/Q

–

Ifter Party
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Submit

Status
Description
I have an Ifter party at the 5th day of Ramadan for the contestants. For this reason I have invited C contestants and arranged P piaju’s (some kind of food, specially made for Ifter). Each contestant ate Q piaju’s and L piaju’s were left (L < Q).

Now you have to find the number of piaju’s each contestant ate.

Input
Input starts with an integer T (≤ 325), denoting the number of test cases.

Each case contains two non-negative integers P and L (0 ≤ L < P < 231).

Output
For each case, print the case number and the number of possible integers in ascending order. If no such integer is found print ‘impossible’.

Sample Input
4
10 0
13 2
300 98
1000 997
Sample Output
Case 1: 1 2 5 10
Case 2: 11
Case 3: 101 202
Case 4: impossible

题目大意 ： 就是有P个单位的食物 有未知人数的人来吃 剩下L个单位的食物 其中没人吃的是一样多的 问每个人吃了多少食物 把每种可能都列举出来(任何一种可能均大于L)
如果没有任何一种可能就输出 impassbale

题解 ： 设 n=P-L 其实就是吧n的所有因子中大于L 的数输出

T只有325个 所以暴力求解即可

for(LL i=1;i*i<=n;i++)
{
if(p%i==0)
{
if(i>l)
a[num++]=i;
if(p/i>l&&p/i!=i) //注意这里 能被开平方的话数就重了 在这wrong 5发 汗！
a[num++]=p/i;
}
}

附本题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <limits.h>
# include <malloc.h>
# include <ctype.h>
# include <math.h>
# include <string>
# include <iostream>
# include <algorithm>
# include <map>
# include <vector>
# include <set>

using namespace std;

# define LL long long int

// 分解因子啊    输出所有大于L的因子

int a[2000000];
int main()
{
    int  t,tt=0,num;
    LL p,l;
    scanf("%d",&t);
    while(t--)
    {
        num=0;
        scanf("%lld%lld",&p,&l);
        printf("Case %d:",++tt);

        p-=l;

        //11
        for(LL i=1;i*i<=p;i++)
        {
            if(p%i==0)
            {
                if(i>l)
                    a[num++]=i;
                if(p/i>l&&p/i!=i)
                    a[num++]=p/i;
            }
        }
        if(!num) printf(" impossible");
        else
        {
            sort(a,a+num);
            for(int i=0;i<num;i++)
                printf(" %d",a[i]);
        }
        printf("\n");
    }
    return 0;
}