 # Some new problems discovered by Chef

For the following problems you MAY assume that Chef is synonymous with Leo.
Problem A: While cooking, Chef thought about the divisors of some odd number N. He noticed that some left remiainder 1 when divided by 4 and others left 3 as a remainder. He then decided that he wanted to find the absolute difference between the number of such divisors of each type modulo 10^9 + 7 Help Chef in finding this answer.
Solve this when N \le 10^{14}.

Problem B. While sleeping, it occured to Chef that the function mapping n \to n^2 is the best and should be honoured. Quickly enough he makes a problem out of it and gives it to Chefu. You are given a positive integer M. Find the number of solutions to x^2 \equiv 1 \pmod {M!} where 1 \le x < M! modulo 10^9 + 7.
Assume M \le 10^{10}.

Problem C. While reading a book, Chef saw that some of the words were “competing” with each other. 2 strings are said to be “competing” if they have the same length and are distinct. Help Chef in determining the number of pairs of “competing” words. Suppose that there are N words in the book and each word has length atmost 10^9. Note that some of these words may be the same as well. Assume N \le 5 \cdot 10^6.

Problem D. In the city of Code Land, there were V cities and E uni-directional roads connecting pairs of them. Each route cost a certain amount of time which is given to you . Chef was in city 1 when he began his journey to city k.
Additionally, each city had a teleporter and it cost a_u money to use it to transport to any other city numbered u. However this did not take any time at all. Now knowing all this and using that Time = Money, chef wants to minimize the amount of time and money he spends on his journey. For example, if he spends T time and M money, then he wants T + M to be minimum. He wants you to tell him what are the values of T and M in the optimal case?
If there are various such cases, then output the one with minimum Money, because even though Money is equal to Time, it is slightly more equal.
Assume V \le 10^3 and E \le \min(\frac{V(V+1)}{2}, 10^5).

2 Likes

Just Bumping it, in case some new viewer wishes to try one of the problems…