本文主要是介绍BUPT OJ181 T-Residual Set，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
Given a pair of number (p,t) where p is a prime and t is a non-negative integer.
The 'Residual Set' of any prime number p is all the integers between 1 and p-1,
that is, '1 2 3 4 ... p-2 p-1'.
What's more, a 'T-Residual Set' of any prime number p means the set of integers below:
'1^T%p 2^T%p 3^T%p 4^T%p ... (p-2)^T%p (p-1)^T%p', where T must be non-negative.
Now for each pair of (p,t), you should calculate how many distinct numbers there are in the 't-Residual Set' of p.
输入格式
A number T(T<=106) in first line.
Then T test cases follow.
Each Test case contains two number p (0<p<10^8) and t (0<t<2^31),
which meanings areaccording to the description.
输出格式
Output T lines.
Each line contains one number, refers to the answer.
Sample Input
输入样例
3
7 9
17 89
47 56输出样例
2
16
23热身赛哪一题来着...已经忘记了= = 蛮有趣的数学题, 解法是推公式
明明组里的大神做出来了结果在比赛快结束的时候居然提交错题目了...嗯, 所以说这题本来也不应该算是我做出来的吧
后来自己还是重新推了一遍, 感觉还好= =
/*
USER_ID: test#birdstorm
PROBLEM: 181
SUBMISSION_TIME: 2014-03-08 01:05:06
*/
#include<stdio.h>
#include<stdlib.h>int GCD(int a,int b)
{int n=a%b;while(n){a=b; b=n;n=a%b;}return b;
}main()
{int T,p,t;scanf("%d",&T);while(T--){scanf("%d%d",&p,&t);printf("%d\n",(p-1)/GCD(t,p-1));}return 0;
}这篇关于BUPT OJ181 T-Residual Set的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
