poj 1091 跳蚤

#include<iostream>#include<algorithm>#include<stdio.h>using namespace std;const int Max = 50;struct data{    int num, v; }fac[Max];bool cmp(data a, data b){    if(a.num < b.num) return true;    else return false;}__int64 mypow(int num, int n){//  求num^n，此时得用到__int64。    __int64 ans = 1;    while(n --) ans *= num;    return ans;}int find_factor(int num){    int i, j, cou = 0;    for(i = 2; i * i < num; i ++)        //  求出num的所有因子(除去1)。        if(num % i == 0){ fac[cou ++].num = i; fac[cou ++].num = num / i;        }    if(i * i == num) fac[cou ++].num = i;//  补sqrt(num)。    fac[cou ++].num = num;    //  补num。    sort(fac, fac + cou, cmp);    for(i = 0; i < cou; i ++){//  求出每个因子的处理值，0为跳过，奇数为-，偶数为+。        bool prime = true;        int k = 0;        for(j = 0; j < i; j ++) if(fac[j].v == 1 && fac[i].num % fac[j].num == 0){     k ++;     prime = false;     if(fac[i].num % (fac[j].num * fac[j].num) == 0){         k = 0;         break;     } }        if(prime) fac[i].v = 1;        else fac[i].v = k;    }    return cou;    // 返回因子的个数。}int main(){    int n, m, cou;    while(scanf("%d %d", &n, &m) != EOF){        cou = find_factor(m);        __int64 sum = mypow(m, n);        for(int i = 0; i < cou; i ++){ if(fac[i].v == 0) continue; else if(fac[i].v % 2 == 1)     sum -= mypow(m / fac[i].num, n); else     sum += mypow(m / fac[i].num, n);        }        printf("%I64dn", sum);    }    return 0;}