Submission #3708

#	Time	Username	Problem	Language	Result	Execution time	Memory
3708		hhosu107	Great Pow! (kriii1_G)	C++98	0 / 1	0 ms	1088 KiB

G

#include <stdio.h>

long long int a , k;
long long int t;
int prime[30];
int eular;
int i, j;

long long int RecurDoubleSquare(long long int n, long long int exp)
{
	long long int temp;
	if (exp == 0){
		return 1;
	}
	else if (exp % 2 == 1){
		temp = RecurDoubleSquare(n, (exp - 1) / 2);
		return n * temp * temp;
	}
	else{
		temp = RecurDoubleSquare(n, exp / 2);
		return temp * temp;
	}
}


int main()
{
	scanf("%lld %lld", &a, &k);
	int b = a +	1;
	for ( i = 2; i * i <= b; ++i ){
		while( b % i == 0 ){
			if(prime[j] == 0)
				prime[j++] = i;
			b /= i;
		}
	}
	if ( j == 0 ) printf("1\n");
	else{ 
		if(b != 1) prime[j++] = b;
		eular = a + 1;
		for(i = 0; i < j; i++)
			eular -= eular / prime[i];
		t = a;
		for(i=0; i<k; i++){
			t %= eular;
			t = RecurDoubleSquare(a, t);
		}
		printf("%lld\n", t);
	}
	return 0;
}

• Subtask 1: 0 / 1