hi everybody ...
i m trying to solve this problem...
For an odd prime p, consider the set A = {1, 2, 3
, p-1}. These set
of numbers
are coprime to p. The order of an integer k, ordp(k), is defined as the
least positive
interger e, where e >= 1 and k^e leaves a remainder 1 when divided by p. The
sum of
orders of all the elements in the set A is the number, S, that p is mapped
to in the
substitution scheme (it is assured all elements will have an order in this
scenario).
Santiago helped Langdon by computing the value of S given a prime number p.
Input: The first line specifies the number of test cases.
Each test case is single odd prime number specified on a new line
p <= 2^63 -1
Use 64-bit integers, if necessary.
Output: For each test case, display on a new line the number, s, with which
p is to be
substituted.
Sample input:
3
3
5
7
Sample output:
3
11
21
Note: Use %lld for printing long long int.
for
k^e%p==1
i found that e will divide p-1(fermate theorem a^(p-1)%p==1 if p is
prime )
i have to find minimum value of e ??
what i did is i started to increase the value of e from 1 to p-1 and and chk
that k^e%p==1;
for(e=1;e<=p-1;e++)
if((p-1)%e==0)
exponetion(k,e,p)//to calculate k^emodp;
but this methos consumes to much time almost it will be TLE ..so plz
sugeest me some algorithm ..
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
