1. Easy but need to careful.
2. One can easily stuck with the question the algorithm O(N*K*K*K) is TLE, so i think about bruto-force solution & some tricks to reduce a factor K: filling the table and using accumulative sum, it helps reduce the complexity to O(N*K*K) and AC.
3. Ok, they require to calculate the number of (A,B,C) with 1<=A,B,C<=N && A!=B*C && d(A)=d(d(B)*d(C)).
so for each number A from 1 to N, i calculate the number of pairs (B,C) which d(d(B)*d(C))=d(A); and minus the number of divisors of A.
However, wrong initialization leads to WA. It needs to correct one line of the code. After correct it, it passes in 80mss.
But a bruto-force to calculate the numbers of divisor of a number x (go from 1 to y=sqrt(x)) can leads to TLE? I check with N=1000000 and it runs about 2,3s or more in my computer (dual core T2300). SO i use "multiplicative property" to calculate these numbers but it is needed or not?
4,5. Have not read the statements because it must be harder than C.
2. One can easily stuck with the question the algorithm O(N*K*K*K) is TLE, so i think about bruto-force solution & some tricks to reduce a factor K: filling the table and using accumulative sum, it helps reduce the complexity to O(N*K*K) and AC.
3. Ok, they require to calculate the number of (A,B,C) with 1<=A,B,C<=N && A!=B*C && d(A)=d(d(B)*d(C)).
so for each number A from 1 to N, i calculate the number of pairs (B,C) which d(d(B)*d(C))=d(A); and minus the number of divisors of A.
However, wrong initialization leads to WA. It needs to correct one line of the code. After correct it, it passes in 80mss.
But a bruto-force to calculate the numbers of divisor of a number x (go from 1 to y=sqrt(x)) can leads to TLE? I check with N=1000000 and it runs about 2,3s or more in my computer (dual core T2300). SO i use "multiplicative property" to calculate these numbers but it is needed or not?
4,5. Have not read the statements because it must be harder than C.
Solution for E: http://graal.ens-lyon.fr/~yrobert/algo/coins2.ps
2.
My solution have complexity O( n*k*(k-m)*m ) ( n*k*k/2*(k/2+1) for worse case ) and passes in 500 ms. =)
so the strategy is: check a bruto force first, if it works we move to next problem?
And your complexity is max(O( n*k*(k-m)*m ),O ( n*k*k/2*(k/2+1) )?