[原创]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;
}