1 int gcd(int a,int b)  //最大公約數
2 {
3     return (b>0)?gcd(b,a%b):a;
4 }

1 int gcd(int a,int b)  //最大公約數
2 {
3     return (b>0)?gcd(b,a%b):a;
4 }
5 int lcm(int a,int b)
6 {
7     return a*b/gcd(a,b);  //最小公倍數
8 }

1 bool cmp(int a,int b)   //   sort降序
2 {
3     return a>b;
4 }

 1 ll pow1(ll a,ll b,ll mod)      //a為底數，b為指數，mod為模
 2 {
 3     ll ans = 1%c;
 4     a = a % mod;
 5     while(b)
 6     {
 7         if(b & 1) ans = ans * a % mod;
 8         b = b>>1;
 9         a = (a * a) % mod;
10     }11     return ans;
12 }

bool prime(int a)
{
    for(int i=2;i<=sqrt(a);i++)
    {
        if(a%i==0) return 0;
    }
    return 1;
}

bool isprime(int n)
{
    if (n<=1)
        return false;
    for (int i=2; i*i<=n; i++)
        if (n%i==0)
            return false;
        return true;
}

int prime[maxn];//存放每個質數，其中prime[0]表示2~maxn范圍內的質數的個數
int visit[maxn];//對每個數進行判斷，0表示質數
void Prime(){
    memset(visit,0,sizeof visit);
    memset(prime, 0,sizeof prime);
    for (int i = 2;i <= maxn; i++) {
        cout<<" i = "<<i<<endl;
        if (!visit[i]) {
            prime[++prime[0]] = i;      //紀錄素數， 這個prime[0] 相當于 cnt，用來計數
        }
        for (int j = 1; j <=prime[0] && i*prime[j] <= maxn; j++) {
            visit[i*prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}