lightoj1116

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1116 - Ekka Dokka

They want to divide the cake such that N * M = W, where W is the dashing factor set by them. Now you know their dashing factor, you have to find whether they can buy the desired cake or not.Ekka and his friend Dokka decided to buy a cake. They both love cakes and that's why they want to share the cake after buying it. As the name suggested that Ekka is very fond of odd numbers and Dokka is very fond of even numbers, they want to divide the cake such that Ekka gets a share of N square centimeters and Dokka gets a share of M square centimeters whereN is odd and M is even. Both N and M are positive integers.

Input

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

Each case contains an integer W (2 ≤ W < 2⁶³). And W will not be a power of 2.

Output

For each case, print the case number first. After that print "Impossible" if they can't buy their desired cake. If they can buy such a cake, you have to print N and M. If there are multiple solutions, then print the result where M is as small as possible.

Sample Input	Output for Sample Input
310512	Case 1: 5 2Case 2: ImpossibleCase 3: 3 4

题目类型：位运算

算法分析：直接从小到大枚举所有的合数约数并判断时间复杂度是O(n)的，会TLE。这里使用的方法是首先判断n是否是偶数，如果不是则直接退出判断，输出Impossible；反之则将n左移一位判断移位后的n是否是奇数，如果是则找到，直接退出输出答案即可；反之则继续判断。该方法的时间复杂度也是O(n)的，不过这里的n表示的是输入数的二进制位数，而二进制位数不超过63，所以不会TLE

#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>
using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 10000007;

const int maxn = 1000 + 66;

int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        long long n;
        cin >> n;
        cout << "Case " << flag++ << ": ";

        bool is_find = false;
        long long temp = n;

        while (1)
        {
            if (temp & 1)
                break;

            temp >>= 1;
            if (temp & 1)
            {
                is_find = true;
                break;
            }
        }

        if (is_find)
            cout << temp << " " << n / temp << endl;

        else
            cout << "Impossible" << endl;
    }

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>

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 10000007;

const int maxn = 1000 + 66;

int main()

{

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

int t, flag = 1;

cin >> t;

while (t--)

{

long long n;

cin >> n;

cout << "Case " << flag++ << ": ";

bool is_find = false;

long long temp = n;

while (1)

{

if (temp & 1)

break;

temp >>= 1;

if (temp & 1)

{

is_find = true;

break;

}

if (is_find)

cout << temp << " " << n / temp << endl;

else

cout << "Impossible" << endl;

}

return 0;

}

lightoj1113

lightoj1127

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

超客的水墨烟雨

lightoj1116

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论