GetResult.cs

CSharp · Console

/Program.cs

using System;
using System.Numerics;
					
public class Program
{
	// функция Эйлера φ(n)
	static long EulerFunc(long N)
	{
		var result = N;
		for (int i = 2; i <= Math.Sqrt(N); i++)
		{
			if (N % i == 0)
			{
				result -= result / i;
			}
			
			while (N % i == 0)
			{
				N /= i;
			}
		}
		
		if (N > 1)
		{
			result -= result / N;
		}
		
		return result;
	}	
	
	static BigInteger GetResult(int N)
	{
		BigInteger result = 0;
		
		// переменная K равна кол-ву нарезанных колечек
		BigInteger k = 2;
		int up, sq, i;
		up = sq = (int)Math.Sqrt(N);
		if (sq * up == N)
		{
			up--;
		}
		
		// Перебираем делители i числа N от 1 до sqrt(N)
		// Так как если i - делитель N, то N/i также будет делителем числа N
		for (i = 1; i <= up; i++)
		{
			if (N % i == 0)
			{
				var kPow = BigInteger.Pow(k, N / i);
				result = BigInteger.Add(result, BigInteger.Multiply(kPow, EulerFunc(i)));
				
				kPow = BigInteger.Pow(k, i);
				result = BigInteger.Add(result, BigInteger.Multiply(kPow, EulerFunc(N / i)));
			}
		}
		
		// Частный случай: если N - полный квадрат
		if (sq * sq == N)
		{
			var kPow = BigInteger.Pow(k, i);
			var multiple = BigInteger.Multiply(kPow, EulerFunc(i));
			result = BigInteger.Add(result, multiple);
		}
		result = BigInteger.Divide(result, N);
		
		return result;
	}	
	
	public static void Main()
	{
		Console.WriteLine("UniLecs");
		Console.WriteLine(string.Format("Answer = {0}", GetResult(3))); // 4
		Console.WriteLine(string.Format("Answer = {0}", GetResult(4))); // 6
	}
}
;