E. Decryption SOLUTIONS CODEFORCES

Decryption SOLUTIONS CODEFORCES

An agent called Cypher is decrypting a message, that contains a composite number nn. All divisors of nn, which are greater than 11, are placed in a circle. Cypher can choose the initial order of numbers in the circle.

In one move Cypher can choose two adjacent numbers in a circle and insert their least common multiple between them. He can do that move as many times as needed.

A message is decrypted, if every two adjacent numbers are not coprime. Note that for such constraints it’s always possible to decrypt the message.

Find the minimal number of moves that Cypher should do to decrypt the message, and show the initial order of numbers in the circle for that.Input

The first line contains an integer tt (1≤t≤100)(1≤t≤100) — the number of test cases. Next tt lines describe each test case.

In a single line of each test case description, there is a single composite number nn (4≤n≤109)(4≤n≤109) — the number from the message.

It’s guaranteed that the total number of divisors of nn for all test cases does not exceed 2⋅1052⋅105.Output

For each test case in the first line output the initial order of divisors, which are greater than 11, in the circle. In the second line output, the minimal number of moves needed to decrypt the message.

If there are different possible orders with a correct answer, print any of them.

Example

input

3
6
4
30

output

2 3 6 
1
2 4 
0
2 30 6 3 15 5 10 
0

Note

In the first test case 66 has three divisors, which are greater than 11: 2,3,62,3,6. Regardless of the initial order, numbers 22 and 33 are adjacent, so it’s needed to place their least common multiple between them. After that the circle becomes 2,6,3,62,6,3,6, and every two adjacent numbers are not coprime.

In the second test case 44 has two divisors greater than 11: 2,42,4, and they are not coprime, so any initial order is correct, and it’s not needed to place any least common multiples.

In the third test case all divisors of 3030 greater than 11 can be placed in some order so that there are no two adjacent numbers that are coprime.

Solution:

Program C++:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(x,y) memset(x,y,sizeof(x))
const int M=2e5+10;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
const int bit=32;
const double pi=acos(-1.0);
set<int>s;
vector<int>ans;
int v[M];
map<int,int>m;
int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		ans.clear();
		for(int i=2;i*i<=n;i++){
			if(n%i==0){
				s.insert(i);
				s.insert(n/i);
			}
		}
		s.insert(n);
		ans.push_back(*s.begin());
		s.erase(s.begin());
		while(s.size()){
			for(set<int>:: iterator it=s.begin();it!=s.end();it++){
				int x=*it;
				if(gcd(ans.back(),x)>1){
					ans.push_back(x);
					s.erase(x);
					break;
				}
			}
		}
		int len=ans.size();
		for(int i=0;i<len;i++){
			printf(i==len-1?"%d\n":"%d ",ans[i]);
		}
		if(gcd(ans[0],ans[len-1])==1){
			puts("1");
		}
		else
		puts("0");
	}
	return 0;
}

Program Java:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class pb5 {
	static ArrayList<Factor> fs;
	static StringBuilder sb;
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int t = in.nextInt();
		for (int ti = 0; ti < t; ti++) {
			int n = in.nextInt();
			int sr = (int) Math.sqrt(n);
			fs = new ArrayList<>();
			int cnt = 0;
			while (n % 2 == 0) {
				cnt++;
				n /= 2;
			}
			if (cnt > 0) fs.add(new Factor(2, cnt));
			for (int i = 3; i <= sr; i+=2) {
				cnt = 0;
				while (n % i == 0) {
					cnt++;
					n /= i;
				}
				if (cnt > 0) fs.add(new Factor(i, cnt));
			}
			if (n > 1) fs.add(new Factor(n, 1));
			
			Collections.sort(fs);
			int fsz = fs.size();
			int need = -1;
			sb = new StringBuilder();
			if (fs.size() == 1) {
				int cf = fs.get(0).n;
				int cur = 1;
				for (int i = 1; i <= fs.get(0).c; i++) {
					cur *= cf;
					sb.append(cur).append(" ");
				}
				need = 0;
			} else if (fs.get(0).c == 1) { // no power more than 1
				if (fs.size() == 2) {
					need = 1;
					int f1 = fs.get(0).n, f2 = fs.get(1).n;
					sb.append(f1).append(" ").append(f2).append(" ").append(f1*f2);
				} else {
					need = 0;
					for (int i = 0; i < fsz-1; i++) {
						int cf = fs.get(i).n;
						sb.append(cf).append(" ");
						for (int j = i+2; j < (i == 0 ? fsz-1 : fsz); j++) {
							int nf = fs.get(j).n;
							sb.append(cf*nf).append(" ");
						}
						sb.append(cf*fs.get(i+1).n).append(" ");
					}
					sb.append(fs.get(fsz-1).n).append(" ").append(fs.get(fsz-1).n*fs.get(0).n).append(" ");
					fdfs(0, 1, 0);
				}
			} else {
				need = 0;
				for (int i = 0; i < fsz-1; i++) {
					Factor cff = fs.get(i);
					int cf = cff.n;
					sb.append(cf).append(" ");
					if (cff.c > 1) {
						sb.append(cf*cf).append(" ");
					}
					for (int j = i+2; j < (i == 0 ? fsz-1 : fsz); j++) {
						int nf = fs.get(j).n;
						sb.append(cf*nf).append(" ");
					}
					sb.append(cf*fs.get(i+1).n).append(" ");
				}
				Factor lf = fs.get(fsz-1);
				sb.append(lf.n).append(" ");
				if (lf.c > 1) sb.append(lf.n*lf.n).append(" ");
				if (fsz > 2) sb.append(fs.get(fsz-1).n*fs.get(0).n).append(" ");
				fdfs(0, 1, 0);
			}
			
			System.out.println(sb.toString().trim());
			System.out.println(need);
		}
		in.close();
	}
	
	static void fdfs(int i, int num, int cnt) {
		if (i >= fs.size()) {
			if (cnt >= 3) sb.append(num).append(" ");
			return;
		}
		fdfs(i+1, num, cnt);
		Factor cf = fs.get(i);
		for (int j = 1; j <= cf.c; j++) {
			num *= cf.n;
			fdfs(i+1, num, cnt+j);
		}
	}
	
	static class Factor implements Comparable<Factor> {
		int n, c;
		public Factor(int n, int c) {
			this.n = n;
			this.c = c;
		}
		@Override
		public int compareTo(Factor o) {
			return o.c-c;
		}
	}
}

Program Python:

t=int(input())
from math import sqrt,floor
for i in range(t):
    N=int(input())
    n=N
    p={}
    for k in range(2,floor(sqrt(n))+1):
        if N%k==0:
            cnt=0
            while N%k==0:
                cnt+=1;N//=k
            p[k]=cnt
    if N!=1:p[N]=1
    if len(p)==1:
        k=tuple(p.keys())[0]
        print(*[k**i for  i in range(1,p[k]+1)])
        print(0)
    elif len(p)==2:
        a,b =p.keys()
        if p[a]==p[b]==1:
            print(a,b,n)
            print(1)
        else:
            if p[a]==1:a,b=b,a
            A=[n]+[a**i for i in range(1,p[a]+1)]+[(a**i)*(b**j) for i in range(1,p[a]+1)for j in range(1,p[b]+1)if(i!=p[a]or j!=p[b])]+[b]

            print(*A)
            print(0)
    else:
        ites=sorted(p.items(),key=lambda x:x[1])
        if ites[-1][1]==1:
            a,b,c,*ites=ites

            a,b,c=a[0],b[0],c[0]
            A=[a*b*c,1,a,a*b,b,b*c,c,c*a]
        else:
            ka,va=ites.pop()
            A=[ka,1]+[ka**i for i in range(2,va+1)]

        for k,v in ites:A+=[a * k**i for i in range(1,v+1) for a in A]
        A.reverse()
        x=A.pop()
        A.pop()
        print(*A,x);print(0)

Related : 

Leave a Comment