ACM 수론에서 흔히 볼 수 있는 템플릿과 결론

1: 최대 공약수의 구법
유클리드 알고리즘 실현.차례로 실현되다

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<iostream>
 5 using namespace std;
 6 __int64 gcd(__int64 y,__int64 x)
 7 {
 8     __int64 ans=0;
 9     if(x==0)
10      ans=y;
11      else
12      ans=gcd(x,y%x);
13      return ans;
14 } 
15 int main()
16 {
17     int t;
18     __int64 A,B;
19     scanf("%d",&t);
20         scanf("%I64d %I64d",&A,&B);
21         if(A>B)
22         swap(A,B);
23         printf("%I64d
",gcd(A,B));
24     }
25     return 0;
26 }

2: 최소 공배수와 최대 공약수의 관계
n과 m의 최대 공약수는 p이고 최소 공배수는 q라면 아래의 관계가 있다
p*q=n*m, 그래서 두 수를 구하는 최대 공약수는 두 수를 구하는 최대 공약수로 바꾸고 둘 사이의 관계에 따라 최소 공약배수==
3: 소수의 판정
1>시상법

int is_prime()
{
for(int i=2;i*i<=n;i++)
{
    if(n%i==0)
    return 0;
} 
return 1;
}

2>필터링
수조 a[]는 1000000 이내의 소수를 저장한다

int get_prme()
{
    int k=0; 
    for(int i=2;i<=1000000;i++)
    {
        if(!chick[i])
        a[k++]=i;
        for(int j=0;j<k;j++)
        {
            if(i*a[j]>1000000) 
            break;
            chick[a[j]*i]=1;
            if(i%a[j]==0)
            break;
        }
    }
    return 0;
} //  

3: 하나의 수의 질인자를 분해하는데 그 중에서 a[]는 소수이고 f[]는 어떤 수의 질인자=

int get_fx(int x)
{
     int j,k=0;
     for( j=0;a[j]*a[j]<=x;j++) 
     {
         if(x%a[j]==0)
        f[ k++]=a[j];
         while(x%a[j]==0)
         {
          x=x/a[j];
          f[k++]=a[j];
        }
        if(x==1)
        break; 
     }
     if(x!=1)
     f[k++]=x;
     return 0
}

4: 11에 의해 정렬될 수 있는 숫자 그가 만족할 수 있는 절대값은 11에 의해 정렬될 수 있다 =
5: 빠른 멱 알고리즘

 1 int qPow(int A, int n)
 2 {
 3     if (n == 0) return 1;
 4     int rslt = 1;
 5 
 6     while (n)
 7     {
 8         if (n & 1) // n 
 9         {
10             rslt *= A%10;
11         }
12         A *= A;
13         n >>= 1;
14     }
15     return rslt%10;
16 }

빠른 멱 알고리즘을 활용하면 n^n을 구하는 복잡도를logn까지 설명할 수 있다.
6: n^n의 개수를 구하다
여러분의 수가 들어오지 않았기 때문에 시계를 통해 n의 여러분수가 0, 1, 2, 5, 6, 7이면 몇 번이든 멱의 한 자릿수는 그 자신==
그리고 저희가 다른 걸 볼게요.
2:4 6 8 2
3:3 9 7 1
4:6 4 6 1
8:4 2 6 8
9:1 9 1 9
위의 수진은 n의 개수가 2, 3, 4, 8, 9이면 n차멱 이후의 결과 변화를 나타낸다. 그리고 네 개의 수만 변화하기 때문에 우리는 n% 4를 고려한다. 그리고 n% 4의 결과는 0, 2...
그래서 위에서 말한 바와 같이 우리는 아래의 수조를 얻어낼 수 있다

1 int data[10][4]={{0,0,0,0},{1,1,1,1},{6,6,4,4},{3,3,7,7},{6,4,6,4},{5,5,5,5,},{6,6,6,6},{7,7,3,3},{6,6,4,4},{1,9,1,9}};

다음은 전체 코드를 제시합니다

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int data[10][4]={{0,0,0,0},{1,1,1,1},{6,6,4,4},{3,3,7,7},{6,4,6,4},{5,5,5,5,},{6,6,6,6},{7,7,3,3},{6,6,4,4},{1,9,1,9}};
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    printf("%d
",data[n%10][n%4]);
    return 0;
} 

블로그 참조http://m.blog.csdn.net/blog/chenminghe271/6766472
7:n의 곱하기 뒤에 있는 0
표를 작성하면 n의 계승 뒤의 0이 아래의 법칙을 나타낸다는 결론을 얻을 수 있다
0 0,1 0,2 0,3 0,4 0,5 1,6 1,7 1,8 1,9 1,10 2,11 2,13 2,14 2,15 3,16 3,17 3,18 3,19 3,20 4;ps(112는 11의 계승 뒤에 2개의 0이 있음을 나타낸다) 다섯 개당 0의 수는 +1이 된다
저희가 25를 진행한 건 25를 발견한 거예요!뒤에는 6개의 0이 있고, 24의 계승 뒤에는 4개의 0이 있다.이곳에 돌연변이가 생겼다. 평상시의 +1이 아니라 +2다.그리고 5와 관련된 차방멱의 수는 모두 돌변한다.
그 돌연변이의 법칙은 바로 1+n(n은 m를 나타내고 이 수는 5^m로 나타낼 수 있다...

#include<stdio.h>
#include<string.h> 
#include<algorithm>
#include<iostream>
#include<stack>
#include<set>
#include<queue>
#include<math.h>
#define maxn 100000
#define long long LL 
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    int sum=0;
    int i=1;
    int ans=0;
    while(sum<n)
    {
           ans+=n/pow(5,i);
           sum=pow(5,i);
           i++;
    }
    printf("%d
",ans);
    return 0;
}

8: 빠른 멱 여분
스피드 멱 여분 은 사실 스피드 멱 을 구할 때 매 걸음 마다 여분 을 구하는 것 이다

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int qpow(int x,int a,int p)
{
    int ans=1;
    x=x%p;
    while(a>0)
    {
        if(a&1)
        ans=(ans*x)%p;
        x=(x*x)%p;
        a>>=1;
    }
    return ans;
}
int main()
{
    int A,B,C;
    scanf("%d %d %d",&A,&B,&C);
    printf("%d
",qpow(A,B,C));
    return 0;
}// A^B%C