CSharp · Console
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
}
}