Pow

제목 설명
a ^ b 를 a 의 b 제곱 으로 정의 하고 ^ 는 오른쪽 결합 을 만족 시 키 는 것, 즉 a ^ b ^ c ^ d = a ^ (b ^ (c ^ d) 입 니 다.예 를 들 어 2 ^ 3 ^ 2 = 2 ^ (3 ^ 2) = 2 ^ 9 = 512.현재 n 개의 수 a1, a2,..., an 은 a1 ^ a2 ^... ^ an 대 p 모델 의 값 을 구 합 니 다.
사후
Drin_E. 할 아버 지 는 다음 방법 이 잘못 되 었 다 는 것 을 알 게 되 었 다.아, 몰라.
한 가지 물건
우 리 는 x% p 를 어떻게 계산 하 는 지 만 고려 하면 이 문 제 를 해결 할 수 있다. p) dx∗a′x≡ans(mod 진짜. 좋 을 것 같 아.ϕ(p′)≡1(mod 좋 을 것 같 아. 그럼 우리 x% 계산 할 수 있어.ϕ좋 을 것 같 아.ϕ(p′)−1(mod p′) 
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxd=10000000+10;
int pri[maxd],phi[maxd],b[30];
bool bz[maxd];
int i,j,k,l,t,n,m,p,top,ca;
int quicksortmi(int x,int y,int p){
    if (!y) return 1;
    int t=quicksortmi(x,y/2,p);
    t=(ll)t*t%p;
    if (y%2) t=(ll)t*(x%p)%p;
    return t;
}
int gcd(int a,int b){
    if (!b) return a;else return gcd(b,a%b);
}
int solve(int i,int p){
    if (i==n+1) return 1;
    int a=b[i],d=gcd(a,p);
    a/=d;p/=d;
    int x=solve(i+1,phi[p]);
    int t=quicksortmi(a,x,p);
    if (x) t=(ll)t*quicksortmi(d,x-1,p)%p;else t=(ll)t*quicksortmi(d,phi[p]-1,p)%p;
    return t*d;
}
int main(){
    phi[1]=1;
    fo(i,2,maxd-10){
        if (!bz[i]){
            pri[++top]=i;
            phi[i]=i-1;
        }
        fo(j,1,top){
            if ((ll)i*pri[j]>maxd-10) break;
            bz[i*pri[j]]=1;
            if (i%pri[j]==0){
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    scanf("%d",&ca);
    while (ca--){
        scanf("%d%d",&n,&p);
        fo(i,1,n) scanf("%d",&b[i]);
        printf("%d
",solve(1,p));
    }
}
비트 연산 은 ACL 권한 수여 와 인증 과정의 원리 분석 을 실현 한다.
2.3.3 동태 계획 - 진급 POJ 1065 1631 3666 2392 2184

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage