A ^ B mod C. (1 < = A, C < = 10000000000, 1 < = B < = 10 ^ 1000000) 를 구하 십시오. (fzu 1759, hdu 3221, hdu 4335)
37166 단어 HDU
빠 른 속도 의 한 문제 라 고 할 수 있 지만, 이곳 의 지수 B 는 매우 크다.공식 이 필요 합 니 다.
A ^ x = A ^ (x% Phi (C) + Phi (C)) (mod C), 그 중 x ≥ Phi (C)
구체 적 으로 볼 수 있 는 ac 대신 블 로그: http://hi.baidu.com/aekdycoin/item/e493adc9a7c0870bad092fd9.수론 은 여러 가지 실패 와 성급 한 성공 을 배 웠 기 때문에 자신의 이 해 는 말 하지 않 겠 습 니 다 ~ 코드 를 직접 올 리 는 것 은 공식 을 직접 사용 하면 됩 니 다.
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<algorithm>
5 #include<cstring>
6 using namespace std;
7 char bb[1000005];
8 __int64 euler(__int64 x){
9 __int64 i, res = x;
10 for(i=2;i<(__int64)sqrt(x*10)+1;i++){//
11 if(x%i==0){
12 res = res /i *(i-1);
13 while(x%i==0) x/=i;
14 }
15 }
16 if(x>1) res = res/x*(x-1);
17 return res;
18 }
19 __int64 quickpow(__int64 m, __int64 n, __int64 k){
20 __int64 b = 1;
21 while(n>0){
22 if(n&1){
23 b = ((b%k)*(m%k))%k;
24 }
25 n = (n>>1);
26 m = ((m%k)*(m%k))%k;
27 }
28 return b;
29 }
30 int main(){
31 __int64 a, c, b, phic, sum;
32 int i, j, k, l;
33 while(~scanf("%I64d",&a)){
34 scanf("%s",bb);
35 scanf("%I64d",&c);
36 l = strlen(bb);
37 phic = euler(c);
38 if(l<=10){
39 b = bb[0]-'0';
40 for(i=1;i<l;i++){
41 b = b*10 + (bb[i]-'0');
42 }
43 if(b<phic){
44 printf("%I64d
",quickpow(a,b,c));continue;
45 }
46 }
47 b = 0ll; //
48 for(i=0;i<l;i++){
49 b = b*10 + (bb[i]-'0');
50 while(b>=phic){ //while ！！！，
51 b -= phic;
52 }
53 /*if(b>=phic){
54 b = b%phic;
55 }*/
56 }
57 printf("%I64d
",quickpow(a,b+phic,c));
58 }
59 return 0;
60 }그리고 09 상하 이 경기 의 문제 (hdu 3221) 도 대체적으로 그렇게 생각 하고 만 들 었 습 니 다. 행렬 의 빠 른 속도 로 구 하 는 피 보 나 절 수열 을 사용 하고 공식 을 사용 합 니 다. 그날 다 쓴 후에 wa 가 되 었 습 니 다. 며칠 후에 돌아 와 보 니 자신 이 행렬 의 빠 른 속도 의 구조 체 변수 에 롱 롱 롱 이 아니 라 int 를 설정 한 것 을 발 견 했 습 니 다. 템 플 릿 도 int 를 사용 해서 초과 하지 않 을 것 이 라 고 생각 합 니 다.나중에 롱 롱 롱 이 A 로 바 뀌 었 는데, 결 과 는 역시 초과 라 는 것 이 증명 되 었 다.내 놓 은 공식 은:
n=1：a
n=2：b
n=3：ab
n=4：ab2
n=5：a2b3
n=6：a3b5
n=7：a5b8
n=8：a8b13
정상 인 들 은 모두 규칙 을 알 수 있 을 것 이다. 바로 피 파 나 절 수열 이다. 지수 가 비교적 크기 때문에 지수 순환 절의 공식 을 사용 해 야 한다. 중간 에 행렬 의 빠 른 속도 로 피 파 나 절 수열 을 구 해 야 한다.구체 적 인 코드:
View Code
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<algorithm>
5 #include<cstring>
6 #include<cmath>
7 using namespace std;
8 __int64 euler(__int64 x){
9 __int64 i, res = x;
10 for(i=2;i<(__int64)sqrt(x*10.0)+1;i++){
11 if(x%i==0){
12 res = res/i*(i-1);
13 while(x%i==0) x/=i;
14 }
15 }
16 if(x>1) res = res/x*(x-1);
17 return res;
18 }
19 __int64 quickpow(__int64 m, __int64 n, __int64 k){
20 __int64 b = 1;
21 while(n>0){
22 if(n&1){
23 b = (b*m)%k;
24 }
25 n = (n>>1);
26 m = (m*m)%k;
27 }
28 return b;
29 }
30 typedef struct{
31 __int64 m[2][2];
32 }Matrix;
33 Matrix P = {0,1,1,1}, I = {1,0,0,1};
34 Matrix matrixmul(Matrix a,Matrix b,__int64 p) //
35 {
36 int i,j,k;
37 Matrix c;
38 for (i = 0 ; i < 2; i++)
39 for (j = 0; j < 2;j++)
40 {
41 c.m[i][j] = 0;
42 for (k = 0; k < 2; k++){
43 c.m[i][j] += (a.m[i][k] * b.m[k][j])%p; //
44 }
45 c.m[i][j] %= p;
46 }
47 return c;
48 }
49
50 Matrix matrix_exp(Matrix P, Matrix I, __int64 n,__int64 p)
51 {
52 Matrix m = P, b = I;
53 while (n >= 1)
54 {
55 if (n & 1)
56 b = matrixmul(b,m,p);
57 n = n >> 1;
58 m = matrixmul(m,m,p);
59 }
60 return b;
61 }
62 int main(){
63 int i, j, k, l, t, T;
64 __int64 a, b, p, n;
65 __int64 f1, f2, f3, phip, aa, bb;
66 scanf("%d",&T);
67 for(t=1;t<=T;t++){
68 scanf("%I64d%I64d%I64d%I64d",&a,&b,&p,&n);
69 phip = euler(p);
70 printf("Case #%d: ",t);
71 if(n==1){
72 printf("%I64d
",a%p);continue;
73 }
74 if(n==2){
75 printf("%I64d
",b%p);continue;
76 }
77 if(n==3){
78 printf("%I64d
",((a%p)*(b%p))%p);continue;
79 }
80 f1 = 0; f2 = 1; k = 0;
81 for(i=4;i<=n;i++){
82 f3 = f1+f2;
83 if(f3>=phip){
84 f3 %= phip;
85 k = 1;break;
86 }
87 f1 = f2; f2 = f3;
88 }
89 Matrix tmp;
90 if(k){
91 tmp = matrix_exp(P,I,n-3,phip);
92 f1 = tmp.m[1][0]; f2 = tmp.m[1][1];
93 aa = f2%phip+phip;
94 f3 = f1+f2;
95 bb = f3%phip+phip;
96 }
97 else{
98 aa = f3;
99 f3 = f1+f2;
100 bb = f3;
101 }
102 printf("%I64d
",(quickpow(a,aa,p)*quickpow(b,bb,p))%p);
103 }
104 return 0;
105 }최근 의 문 제 는 바로 며칠 전에 여러 학교 문 제 를 풀 었 습 니까? 아니면 그 후에 야 비로소 이 공식 을 풀 었 습 니까? 나중에 문 제 를 보고 풀 었 습 니 다. 그 trick 도 보통 사람 을 함정 에 빠 뜨리 는 것 이 아 닙 니 다.
제목: 세 개의 수 를 제시 하 다 (b, P and M), 그 중 (0 < = b < P, 1 < = P < = 10 ^ 5, 1 < = M < = 2 ^ 64 – 1), M 의 범 위 는 unsigned long 을 사용 해 야 한 다 는 것 을 암시 합 니 다. nn 을 만족 시 키 세 요!Ξb (mod p), (0 ≤ n ≤ M) 의 n 은 몇 개 입 니까?또한 큰 정수 멱 으로 그 중에서 지수 가 매우 크기 때문에 앞에서 말 한 지수 순환 절의 공식 을 사용 해 야 한다.
A ^ x = A ^ (x% Phi (C) + Phi (C)) (mod C), 그 중 x ≥ Phi (C)
n 에 대해!의 처 리 는 주로 세 부분 으로 나 뉜 다.
1, n 아주 어 렸 을 때, 직접 매 거 하면 됩 니 다. 아주 작은 것 은 n 입 니 다!
3, 어떤 n 이 되 는 것 을 더 발견 할 수 있 습 니 다!%phip = = 0 시, 그 후의 모든 n!모두 phoip 을 제거 할 수 있 습 니 다. 상기 공식 은 N 과 같 습 니 다!ΞnphipΞb (mod p), 지 수 는 고정 값 입 니 다. 이렇게 하면 순환 절의 공식 을 알 수 있 습 니 다. 곱셈 동 여 식 (shit, 이것 도 오래 봤 습 니 다. phip 개 n 상승) nphipΞ(n%p)phipΞb (mod p), 그러므로 p 개 n 을 매 거 하면 됩 니 다. 그 중 어느 n 이 성립 되 었 을 때 그 후 ≤ M 의 모든 모 p 동 여 수의 개 수 를 알 수 있 고 답 이 나 옵 니 다.(큰 trick 코드 참조)
1 #include<iostream>
2 #include<cmath>
3 #include<cstdio>
4 #include<cstring>
5 #include<algorithm>
6 #define see(x) cout<<#x<<":"<<x<<endl;
7 using namespace std;
8 typedef unsigned __int64 LLU;
9 LLU euler(LLU x){
10 LLU i, res = x;
11 for(i=2;i<(LLU)sqrt(x*10.0)+1;i++){
12 if(x%i==0){
13 res = res/i*(i-1);
14 while(x%i==0) x/=i;
15 }
16 }
17 if(x>1) res = res/x*(x-1);
18 return res;
19 }
20
21 LLU quickpow(LLU m, LLU n, LLU k){
22 LLU b = 1;
23 while(n>0){
24 if(n&1)
25 b = (b*m)%k;
26 n = n>>1;
27 m = (m*m)%k;
28 }
29 return b;
30 }
31 LLU f[100001];
32 int main(){
33 //freopen("1005.in","r",stdin);
34 //freopen("out.txt","w",stdout);
35 int t, T, i , k, l, flag;
36 LLU b, p, m, phip, ans;
37 scanf("%d",&T);
38 for(t=1;t<=T;t++){
39 ans = 0; flag = 0;
40 //cin>>b>>p>>m;
41 scanf("%I64u%I64u%I64u",&b,&p,&m);
42 if(b==0&&p==1&&m==18446744073709551615ull){
43 printf("Case #%d: 18446744073709551616
",t);continue;
44 }// trick，m==18446744073709551615 2^64-1， b==0，p==1， [0,m] 1 0， 2^64 ， 2^64 unsigned long long，
45 phip = euler(p);
46 f[0] = 1;
47 if(b==0){
48 ans++;
49 }
50 for(i=1;i<=m;i++){
51 f[i] = f[i-1]*i;
52 if(f[i]>=phip){
53 f[i] = f[i]%phip;
54 flag = 1;
55 if(f[i]==0){
56 break;
57 }
58 }
59 if(flag){
60 if(quickpow(i,f[i]+phip,p)==b){
61 ans++;
62
63 }
64 }
65 else{
66 if(quickpow(i,f[i],p)==b){
67 ans++;
68 }
69 }
70 }
71 for(k=0;i<=m&&k<p;i++,k++){
72 if(quickpow(i,phip,p)==b){
73 ans = ans+1+(m-i)/p;
74 }
75 }
76 printf("Case #%d: %I64u
",t,ans);
77 //cout<<ans<<endl;
78 }
79 return 0;
80 }이 문 제 를 이용 하여 항 저 우 전기 oj 를 직접 측정 하면 long long 을 정의 할 수 있 습 니 다. 입 출력 만% lled 를 사용 할 수 없고 cin, cout 를 사용 할 수 있 습 니 다. scanf 를 사용 하면 printf 는% I64d 만 사용 할 수 있 기 때문에int64。long long 과 함께 unsigned 를 정의 할 수 있 습 니 다.int 64, 입 출력 은% I64u 를 사용 할 수 있 습 니 다.
수론 문제 에 대한 총 결:
1. 수론 문제, 코드 가 길지 않 습 니 다. 일반적으로 관련 지식 을 알 고 있 으 면 구 해 낼 수 있 습 니 다. 그러나 부주의 로 형 주 를 잃 지 않도록 디 테 일 에 도 주의해 야 합 니 다 ~ ~
2. 수학 문제 이후 모든 변 수 를 long 으로 설정 합 시다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
