elevator-manager

View Russian Translation

In this problem the goal is to implement a program managing an elevator designed especially for mathematicians.

The elevator can go to any of N floors numbered from 1 to N and it can carry an arbitrary number of people at one time. 

Initially the elevator is at floor 1, without any people inside, and it can go to any floor from 1 to N at any time. The total distance the elevator travels is defined as the sum of distances between the consecutive floors it went to in the whole process, and the distance between two floors F_1 and F_2 is defined as |F_1 - F_2|.

In addition, there are Q events which are about to happen consecutively starting from now. There are two types of events to handle:
entry(F, K) - K people are waiting to enter the elevator at floor F
exit(F, K) - K people are waiting to exit the elevator at floor F

The elevator must handle events in the order they come, and must handle only the events which are possible.

An entry event entry(F, K) is possible if and only if X = F + K is a prime number.

An exit event exit(F, K) is possible if and only if X = F + K has odd number of divisors.

If the elevator being currently on floor F_1 has to handle an event taking place on floor F_2, it must first go from floor F_1 to floor F_2 moving up and/or down in any possible way, and it can handle the event only while it is at floor F_2.

The task in this problem is to print the minimum distance that the elevator has to travel to handle all possible events in the order they come and the number of people inside the elevator after handling the last possible event. Since the total distance can be very large, output it modulo 10^9 + 7.

Constraints:
1 ≤q N ≤q 10^{12}  
1 ≤q Q ≤q 10^5  
1 ≤q F ≤q N  
1 ≤q K ≤q 10^6  
for an exit event exit(F, K), parameter K is not greater than the number of people in the elevator just before that event

Input format:

In the first line there are two integers N and Q denoting the number of floors and the number of events. In the following Q lines the descriptions of Q events in the order they come are given. Each single event is given by 3 space separated integers T, F, K, where T is either 1 or 2 and denotes the type of the event (1 stands for an entry event, 2 stands for an exit event), F denotes the number of floor where this event has to be handled if it is a possible event, and K denotes the number of people in this event.

Output format:

In a single line output two space separated integers D, K denoting the minimum total distance the elevator travels to handle all possible events taken modulo 10^9 + 7, and the number of people in the elevator after the last handled event.

SAMPLE INPUT
10 2
1 2 3
2 6 2

SAMPLE OUTPUT
1 3

Explanation

Initially the elevator is at floor 1 with no people inside. The first event is an entry event at floor 2 with 3 people wanting to enter the elevator. Is is a possible event, because 2 + 3 = 5 is a prime number, so the elevator must go to the 2nd floor to handle this event. However, the second event is not possible, because it is an exit event and 6 + 2 = 8 has 4 divisors, which is an even number. Finally, the elevator must handle only the first event, and the minimal distance it need to cover to do that is 1 and the number of people after handling this event inside the elevator is 3.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import math
HUGE = 10**9 + 7

def _try_composite(a, d, n, s):
	if pow(a, d, n) == 1:
		return False
	for i in range(s):
		if pow(a, 2**i * d, n) == n-1:
			return False
	return True # n  is definitely composite
 
def is_prime(n, _precision_for_huge_n=16):
	if n in _known_primes or n in (0, 1):
		return True
	if any((n % p) == 0 for p in _known_primes):
		return False
	d, s = n - 1, 0
	while not d % 2:
		d, s = d >> 1, s + 1
	# Returns exact according to http://primes.utm.edu/prove/prove2_3.html
	if n < 1373653: 
		return not any(_try_composite(a, d, n, s) for a in (2, 3))
	if n < 25326001: 
		return not any(_try_composite(a, d, n, s) for a in (2, 3, 5))
	if n < 118670087467: 
		if n == 3215031751: 
			return False
		return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7))
	if n < 2152302898747: 
		return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11))
	if n < 3474749660383: 
		return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13))
	if n < 341550071728321: 
		return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17))
	# otherwise
	return not any(_try_composite(a, d, n, s) 
				   for a in _known_primes[:_precision_for_huge_n])
 
_known_primes = [2, 3]

def NumOfDivisor(n):
	root_n = int(n**0.5)
	return root_n**2 == n

def is_possible(typ, floor, people):
	if typ == 1:
		return is_prime(floor + people)
	elif typ == 2:
		return NumOfDivisor(floor + people)
	
if __name__ == '__main__':
	presentFloor, total_persons, distance = 1, 0, 0
	floors, events = list(map(int, input().split()))
	for _ in range(events):
		typ, floor, people = list(map(int, input().split()))
		if is_possible(typ, floor, people):
			distance = distance + abs(presentFloor - floor)
			if typ == 1:
				total_persons += people
			elif typ == 2:
				total_persons -= people
			presentFloor = floor
	print(distance % HUGE, total_persons)


from sys import stdin
import math
import random
def mod(a,b,c):
	if b==0:
		return 1
	if b<=10:
		return (a**b)%c
	if b%2==1:
		return (a*mod(a,b-1,c))%c
	x=mod(a,b/2,c)
	return (x*x)%c
	
def check(p):
	if p<=1:
	return 0
	if p==2:
	return 1;
	if p%2==0:
	return 0
	count = 10
	s=p-1
	while s%2==0:
	s=s/2;
	for i in range(0,count):
	a=random.randint(1,p-1)
	temp = s
	x=mod(a,temp,p) 
	while(temp!=p-1 and x!=1 and x!=p-1):
        		x=(x*x)%p
           	 	temp *= 2;
	if(x!=p-1 and temp%2==0):
		return 0
	return 1
def ch(m):
	n = int(math.sqrt(m))
	return n*n==m
ans = 0
hi = 10**9 + 7
n,q = list(map(int,stdin.readline().split()))
a = stdin.readlines()
st = 1
pep = 0
for i in a:
	ty,f,k = list(map(int,i.split()))
	if ty==1:
	if check(f+k):
		pep+=k
		if f>st:
		ans+= f-st
		else:
		ans+= st-f
		st = f
	else:
	if ch(f+k):
		pep -= k
		if f>st:
		ans+= f-st
		else:
		ans+=st-f
		st = f
print(ans%hi,pep)