lightoj1014

maksyuki 发表于 oj 分类，标签: 数论-因子个数

27 8月 2015

1014 - Ifter Party

Now you have to find the number of piaju's each contestant ate.I have an Ifter party at the 5^th 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).

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 < 2³¹).

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	Output for Sample Input
410 013 2300 981000 997	Case 1: 1 2 5 10Case 2: 11Case 3: 101 202Case 4: impossible

题目类型：因子个数

算法分析：直接枚举小于sqrt(P - L)的所有因子，然后生成大于sqrt (P – L)的所有因子，注意枚举因子中的下标i必须使用long long类型，否则会RE

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 200000 + 66;

long long ans[maxn], len;


int main()
{
//    ifstream cin ("aaa.txt");
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d:", flag++);

        long long P, L;
        scanf ("%lld%lld", &P, &L);

        long long val = P - L;

        if (val <= L)
        {
            puts (" impossible");
            continue ;
        }

        len = 0;
        for (long long i = 1; i * i <= val; i++)
        {
            if (val % i == 0)
            {
                if (i > L)
                    printf (" %lld", i);

                if (i * i == val)
                    continue;

                ans[len++] = i;
            }
        }

        for (long long i = len - 1; i >= 0; i--)
            if (val / ans[i] > L)
                printf (" %lld", val / ans[i]);


        puts ("");
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 200000 + 66;

long long ans[maxn], len;

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d:", flag++);

long long P, L;

scanf ("%lld%lld", &P, &L);

long long val = P - L;

if (val <= L)

{

puts (" impossible");

continue ;

}

len = 0;

for (long long i = 1; i * i <= val; i++)

{

if (val % i == 0)

{

if (i > L)

printf (" %lld", i);

if (i * i == val)

continue;

ans[len++] = i;

}

for (long long i = len - 1; i >= 0; i--)

if (val / ans[i] > L)

printf (" %lld", val / ans[i]);

puts ("");

}

return 0;

}

lightoj1012

lightoj1016

一	二	三	四	五	六	日
« 6月
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

超客的水墨烟雨

lightoj1014

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论