短除法对一个数分解质因数

把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。

分解质因数只针对合数（质数就只有本身和1两个因数，不能分解）。一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式叫短除法.

下面给出3种函数，分别对应main函数中3段注释，请读者自行分别运行查看：

#include<iostream>
#include<vector>
#include<map> 
using namespace std;
vector<int> v;
void prime_factor1(int n){
	for(int i=2;i*i<=n;i++){         
		if(n%i==0){
			v.push_back(i); 
	    }
			while(n%i==0){              //计算出所有质因子(每种一个) 
				n/=i;
			}	
	    
	}
	if(n>1) v.push_back(n);         
	
}

vector<int> prime_factor2(int n){        //计算一个数的所有质因子(按顺序给出所有，包含重复的) 
	
	vector<int> ans; 
	for(int i=2;i*i<=n;i++){       
		if(n%i==0){
			//ans.push_back(i); 
	
			while(n%i==0){
				n/=i;
				ans.push_back(i);           //重复的也存起来 
			}	
	    }
	}
	if(n>1) ans.push_back(n);          //最后剩下的这个不能整除2的数，
	                                   //假如是1，说明原来的n就是个2的次方数(2^X) 
	return ans;                        //不是1，那就是n的一个质因子，也存起来 
}

map<int,int> prime_factor3(int n){
	map<int,int> res;
	for(int i=2;i*i<=n;i++){          //用map存储每个质因子及其数量 
		if(n%i==0){                   //用质因子的次方的积来表示 
			while(n%i==0){            //如12 = 2^2 * 3^1; 
				res[i]++;
				n/=i;
			}
		}
	}
	
	if(n!=1) res[n]++;
	return res;
} 

int main(){
	int n;
	while(cin>>n){
	    
//		  v.clear();
//        prime_factor1(n);
//   		for(int i=0;i<v.size();i++){      //这部分对应void prime_factor1(int n) 
//			cout<<v[i]<<" ";
//		    }
//          cout<<endl;		

		
//		vector<int> v=prime_factor2(n);
//		for(int i=0;i<v.size();i++){         //这部分对应vector<int> prime_factor2(int n)
//			cout<<v[i]<<" ";
//		}
//      cout<<endl;  


//        map<int,int> p=prime_factor3(n);;
//        map<int,int>::iterator it;                   //这里用的是质因数幂的乘积表示n 
//        for(it=p.begin();it!=p.end();it++){          //如12 = 2^2 * 3^1; 
//        	cout<<(*it).first<<"^"<<(*it).second<<" ";
//		 } 
//        cout<<endl;
	}
	return 0;
}

裸题：点这里在线提交

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 where N is odd and M is even. Both N and M are positive integers.

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.

Input

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

Each case contains an integer W (2 ≤ W < 263). 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

Sample Output

Case 1: 5 2

Case 2: Impossible

Case 3: 3 4

大意：一个数能不能拆成一奇一偶相乘的形式，不能就输出impossible ;

那就对这个数反复除以2呗（质因子分解），假如除到最后不是1（是1表明这个数是2的次方，不可能拆分成一奇一偶），那就肯定是个奇数。

#include<iostream>
using namespace std;
typedef long long ll;
int main(){
	ll t,n;
	cin>>t;
	static int k=1; 
	while(t--){
		cin>>n;
		ll m=n;
		ll ans=1;
		while(!(n&1)){
			n/=2;
			ans*=2;
		}
		if(ans!=1)
		cout<<"Case "<<k++<<": "<<m/ans<<" "<<ans<<endl;
	    else 
	    cout<<"Case "<<k++<<": "<<"Impossible"<<endl;
	}
	return 0;
}