Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

slow_coder4's blog

How can solve Uva 10692
By slow_coder4, history, 10 years ago, In English

Give me some tips to solve- uva 10692 problem.. - problem link:https://uva.onlinejudge.org/external/106/10692.pdf

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

A ^ x % m = A ^ (x % phi [M] + phi [M]) % m (x >= phi [M]) (phi [M] M is the Euler function)

you can recursively go to solution.

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Why do we need to sum up phi[M] in A ^ (x % phi [M] + phi [M]) % m? Isn't A ^ (x % phi[M]) % m good enough?

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      In case x % φ[M] is equal to 0, A^0 % M will become one, which may not be same as A^φ{M} % M

      e.g. (2 ^ 0) % 10 = 1, (2 ^ 4) % 10 = 6, phi[10] = 4;

      → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Thanks.. if u explain How/Why its works?

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      it is necessary to dfs like that


      int dfs(int i, int mod) {

	if (i == n - 1) {

 		if (a[i] >= mod)
   			return a[i] % mod + mod;

      		return a[i];	

	}

	int k = dfs(i + 1, phi[mod]);
	return pow_mod(a[i], k, mod);

}
      → Reply
  • »
    »
    9 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Can you or someone else please reply why this equation works? Is this true for any A and m ?

    → Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Here's the AC code may help you, be careful that we should test if b in ab is greater than φ(m)

//  Created by Sengxian on 3/1/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  UVa 10692 指数循环节
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

inline int ReadInt() {
	int n = 0, ch = getchar();
	while(!isdigit(ch) && ch != '#') ch = getchar();
	if(ch == '#') exit(0);
	while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
	return n;
}
typedef long long ll;
const int maxm = 10000 + 3, maxn = 10 + 3;
int phi[maxm];
void process() {
	memset(phi, 0, sizeof(phi));
	phi[1] = 1;
	for(int i = 2; i < maxm; ++i) if(!phi[i])
		for(int j = i; j < maxm; j += i) {
			if(!phi[j]) phi[j] = j;
			phi[j] = phi[j] / i * (i - 1);
		}
}

ll mod_pow(ll a, ll b, ll MOD) {
	ll ans = 1;
	for(int i = 0; i < b; ++i) {
		ans *= a;
		if(ans > MOD) break;
		if(i + 1 == b) return ans;
	}
	ans = 1;
	while(b > 0) {
		if(b & 1) ans = ans * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return ans + MOD;
}

int m, n, a[maxn];
//[idx, n)
ll f(ll idx, ll MOD) {
	if(idx == n - 1) return a[idx] < MOD ? a[idx] : a[idx] % MOD + MOD;
	return mod_pow(a[idx], f(idx + 1, phi[MOD]), MOD);
}

int main() {
	process();
	int caseNum = 0;
	while(m = ReadInt(), n = ReadInt(), m + n) {
		for(int i = 0; i < n; ++i)
			a[i] = ReadInt();
		printf("Case #%d: %lld\n", ++caseNum, f(0, m) % m);
	}
	return 0;
}
→ Reply