Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hidden Graph

By Peregrine_Falcon · Limits 2s, 512 MB

There is an unweighted, undirected hidden graph. You are given an integer range from LL to RR. There are total ofRL+1R-L+1 nodes numbered from LL to RR. Two nodes U,VU,V have an edge between them if the GCD(U,V)GCD(U, V) is greater than 11.

You have to find the number of the connected components XX, of this graph and find the size of each component.

An explanation of the unweighted and undirected graph can be found here.
An explanation of the Connected component can be found here.

Input

The first line of the input consists of the number of test case TT (1T10)(1 \leq T \leq 10).
Each test case consists of two integers LL and RR.

For 40 Points: (1LR103)(1 \leq L \leq R \leq 10^3).
For 100 Points: (1LR106)(1 \leq L \leq R \leq 10^6)

Output

The first line of each test case consists of integer XX denoting the number of connected components of the graph.
Then each of the next X lines consists of the size of each component in sorted order.

Sample

InputOutput
2
1 9
2 7
4
1
1
1
6
3
1
1
4


Hidden graph for the first test case:
The greatest common divisor for the following pairs is greater than 1:
(2,4), (2,6), (2,8), (4,6), (4,8), (6,8), (3,6), (3,9), (6,9).
Each pair of nodes above share a common edge between them. So, there are 3 components consists of 1 node and another component with 6 nodes.

Discussion

Statistics


65% Solution Ratio

MeekgeekEarliest, 4M ago

Deshi_TouristFastest, 0.0s

PIS_ShamiLightest, 1.3 MB

deepGooglerShortest, 511B

Submit

Login to submit

Editorial

We can easily precalculate the prime divisors of each number using SieveofEratosthenesSieve of Erato...

Toph uses cookies. By continuing you agree to our Cookie Policy.