数论（二）

作者: 云中翻月 | 来源:发表于2019-10-15 09:48 被阅读0次

模运算

POJ 1150: The Last Non-zero Digit
题解链接 https://blog.csdn.net/Avalon_cc/article/details/79967855
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
题解链接 https://blog.csdn.net/Avalon_cc/article/details/79967855 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
const int mod=10;
int get2(int n){ //n!中因子2的个数 
    if(n==0) return 0;
    return get2(n/2)+n/2;
}
int get5(int n){ //n!中因子5的个数 
    if(n==0) return 0;
    return get5(n/5)+n/5;
}
int g(int n,int x){ //1~n中除去5的奇倍数后，奇数数列末尾为x的数的个数 
    if(n==0) return 0;
    return n/10+(n%10>=x)+g(n/5,x);
}
int getx(int n,int x){ //1~n中除去5的奇倍数后，全数列末尾为x的数的个数 
    if(n==0) return 0;
    return getx(n/2,x)+g(n,x);
}
int table[4][4]={
    {6,2,4,8},  //2^n%10的循环节，注意如果2的个数为0时候，结果应该是1，要特殊处理。
    {1,3,9,7},  //3
    {1,7,9,3},  //7
    {1,9,1,9}   //9
};//3，7，9的循环节中第一位，刚好是1，故不需要考虑这些数字出现次数为0的情况。
int main() {
//  ios::sync_with_stdio(false);
    //freopen("The Last Non-zero Digit.in","r",stdin);
    int n,m;
//  D(get2(20));D(get5(20));D(g(20,3));D(getx(20,3));E; 
    while(cin>>n>>m){
        int num2=get2(n)-get2(n-m);
        int num5=get5(n)-get5(n-m);
        int num3=getx(n,3)-getx(n-m,3);
        int num7=getx(n,7)-getx(n-m,7);
        int num9=getx(n,9)-getx(n-m,9);
        if(num5>num2){
            cout<<5<<endl;
            continue; 
        }
        int ans=1;
        if(num5!=num2){
            ans*=table[0][(num2-num5)%4];
            ans%=mod;
        }
        ans=(ans*table[1][num3%4]%mod*table[2][num7%4]%mod*table[3][num9%4]%mod)%mod;
        cout<<ans<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 1284: Primitive Roots
求原根个数的模板题。
定理：如果p有原根，则它恰有φ(φ(p))个不同的原根（无论p是否为素数都适用）
p为素数，当然φ(p)=p-1,因此就有φ(p-1)个原根。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
求原根个数的模板题。
定理：如果p有原根，则它恰有φ(φ(p))个不同的原根（无论p是否为素数都适用）
p为素数，当然φ(p)=p-1,因此就有φ(p-1)个原根。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
int phi(int n){
    int ans=n;
//  for(int i=2;i<=sqrt(n);i++){ //这样用sqrt，poj会CE
    for(int i=2;i<=(int)sqrt((double)n);i++){  
        if(n%i==0){
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Primitive Roots.in","r",stdin);
    int p;
    while(scanf("%d",&p)!=EOF){
        printf("%d\n",phi(p-1));
    }   
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 2115: C Looooops
$d=exgcd(a,b,x,y)$ 可以求 $gcd(a,b)=d$ ，同时x和y的值就是 $ax+by=1$ 的一组解。
对于该题，相当于求关于x的同余方程 $A+xC≡B(mod\; 2^k)$ 的最小整数解。
对上式变形得， $A+xC=B-y*2^k$ 。即 $xC+y*2^k=B-A$ 。
设 $d=gcd(C,2^k)$ 。根据裴蜀定理，若(B-A)%d==0，则原方程有整数解。
于是先特判是否有解后，在方程两遍同除以d（模数也要除以d）。
最后将exgcd算出的x乘以 $(B-A)/d$ 然后再对 $2^k/d$ 求模即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
d=exgcd(a,b,x,y)可以求gcd(a,b)=d，同时x和y的值就是ax+by=1的一组解。
对于该题，相当于求关于x的同余方程A+xC≡B(mod 2^k)的最小整数解。
对上式变形得，A+xC=B-y*2^k。即xC+y*2^k=B-A。
设d=gcd(C,2^k)。根据裴蜀定理，若(B-A)%d==0，则原方程有整数解。
于是先特判是否有解后，在方程两遍同除以d（模数也要除以d）。
最后将exgcd算出的x乘以(B-A)/d然后再对2^k/d求模即可。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=+5;
const int INF=0x3f3f3f3f;
ll A,B,C,k;
ll exgcd(ll a,ll b,ll& x,ll& y){
    if(!b){
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-a/b*y;
    return d;
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("C Looooops.in","r",stdin);
    while(scanf("%lld%lld%lld%lld",&A,&B,&C,&k)!=EOF){
        if(!A&&!B&&!C&&!k) break;
        ll x,y;
        ll d=exgcd(C,(1ll<<k),x,y);
//      D(d);D(x);D(y);E;
        if((B-A)%d){
            printf("FOREVER\n");
        }
        else{
            ll mod=(1ll<<k)/d;
            ll ans=(x*(B-A)/d%mod+mod)%mod;
            printf("%lld\n",ans);
        }
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3708: Recurrent Function
题解链接 http://www.hankcs.com/program/algorithm/poj-3708-recurrent-function.html
模数和底数不一定互质，所以需要应用多次欧几里得算法。
除此之外，还需要高精度，不想打。
代码如下

POJ 2720: Last Digits
题解链接 https://blog.csdn.net/yuege38/article/details/78989456

a和m不互质的时候的广义欧拉定理
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
题解链接 https://blog.csdn.net/yuege38/article/details/78989456
http://ww3.sinaimg.cn/large/6cbb8645jw1es7p9f2l68j20fm03hdfx.jpg
*/
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<iomanip>
#define int long long
#define re register
using namespace std;
typedef long long ll;
const int maxn=100+5;
int base[10]= {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000};
int tab[maxn][maxn]; //tab[i,j]表示i^i^i...^i(j个i)是否>1e7，是则为-1，否则为i^i^i...^i(j个i)的确切值/上次计算过的答案（用于开始时的判断） 
int fxb[maxn][maxn]; //fxb[i,j]表示i^i^i...^i(j个i)是否>1e7，否则为i^i^i...^i(j个i)的确切值（用于欧拉定理时的递归计算时的判断） 
inline int limit_power(int a,int b) {
    ll res=1;
    for(int i=1; i<=b; ++i) {
        res=res*1ll*a;
        if(res>1e7) return -1;
    }
    return res;
}
void init() {
    memset(tab,-1,sizeof(tab));
    memset(fxb,-1,sizeof(fxb));
    for(int i=1; i<=maxn-5; ++i) {
        tab[i][0]=fxb[i][0]=1;
        for(int j=1; j<=maxn-5; ++j) {
            tab[i][j]=fxb[i][j]=limit_power(i,fxb[i][j-1]);
            if(tab[i][j]==-1) break;
        }
    }
}
inline ll ksm(int x,int b,int mod) {
    ll res=1;
    while(b) {
        if(b&1) res=res*x%mod;
        x=x*x%mod;
        b>>=1;
    }
    return res;
}
inline int get_phi(int x) {
    int ans=x;
    for(int i=2; i*i<=x; ++i) {
        if(x%i==0) {
            ans=ans/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) ans=ans/x*(x-1);
    return ans;
}
/* 
int solve(int b,int a,int mod) {
    if(fxb[b][a]!=-1) return fxb[b][a]%mod;//
    int phi=get_phi(mod);
    if(fxb[b][a-1]!=-1&&fxb[b][a-1]<=phi) return ksm(b,fxb[b][a-1],mod);
    return ksm(b,solve(b,a-1,phi)+phi,mod);
}
*/ 
int solve(int b,int x,int mod) {
    if(fxb[b][x]==-1) {
        int phi=get_phi(mod);
        if(fxb[b][x-1]!=-1&&fxb[b][x-1]<phi) {
            return ksm(b,fxb[b][x-1],mod);
        } else {
            return ksm(b,solve(b,x-1,phi)+phi,mod);
        }
    } else {
        return tab[b][x]%mod;
    }
}
signed main() {
//  ios::sync_with_stdio(false);
    //freopen("Last Digits.in","r",stdin);
    ll b,x,n;
    init();
    while(scanf("%lld",&b)!=EOF) {
        if(!b) break;
        scanf("%lld%lld",&x,&n);
        int res;
        if(tab[b][x]!=-1) { //不需要降幂计算
            res=tab[b][x]%base[n];
        } else {
            tab[b][x]=solve(b,x,1e7); //用欧拉函数降幂 开始递归（由于有多组样例 所以用tab记录下来） 
            res=tab[b][x]%base[n];
        }
        cout<<setfill('0')<<setw(n)<<res<<endl;
    }
    return 0;
}
#endif

矩阵

POJ 2345: Central heating

代码如下

/*
题意：有n个窗口，有n个师傅，每个师傅可以管理很多窗口，可以重复的，给一个师傅下命令，
这个师傅会管理他所有的窗口，如果是关闭的就打开，如果是打开的就关闭，现在想让所有的窗口打开，问你怎么下命令。 
思路：将每个师傅管理的窗口转化成01序列，末尾加0，表示方程的结果，然后凑成矩阵，高斯消元解方程，消元的时候变成异或。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=250+5;
const int INF=0x3f3f3f3f;
int n;
int a[maxn][maxn];//增广矩阵
int x[maxn];//解集
void init(){
    memset(a,0,sizeof(a));
    memset(x,0,sizeof(x));
}
void Gauss(){
    for(int i=1;i<=n;i++){
        int col=-1;
        for(int j=i;j<=n;j++){//找到第一个不为零的行
            if(a[j][i]){
                col=j;
                break;
            }
        }
        for(int j=i;j<=n+1;j++){
            swap(a[i][j],a[col][j]);
        }
        for(int j=i+1;j<=n;j++){
            if(a[j][i]!=0){
                for(int k=i;k<=n+1;k++){
                    a[j][k]^= a[i][k];
                }
            }
        }
    }
    for (int i=n;i>=1;--i){
        x[i] = a[i][n+1];
        for (int j=i-1;j>=1;--j){
            a[j][n+1]^=(x[i]&a[j][i]);
        }
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Central heating.in","r",stdin);
    init();
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int num;
        while(scanf("%d",&num)){
            if(num==-1) break;
//          D(num);D(i);E;
            a[num][i]=1;
        }
        a[i][n+1]=1;
    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    */
    Gauss();
    /*
    for(int i=1;i<=n;i++){
        D(x[i]);
        for(int j=1;j<=n;j++){
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    */
    for(int i=1;i<=n;i++) if(x[i]) printf("%d ",i);
    return 0;
}

POJ 3532: Resistance
在电路中，很难直接根据输入判断每条导线中电流的流向。
因此需要基尔霍夫定律来列出每个点电位的方程。
具体题解链接
https://blog.csdn.net/yuege38/article/details/78946445
http://m.bubuko.com/infodetail-1987259.html
代码如下

/*
在电路中，很难直接根据输入判断每条导线中电流的流向。
因此需要基尔霍夫定律来列出每个点电位的方程。
具体题解链接
https://blog.csdn.net/yuege38/article/details/78946445
http://m.bubuko.com/infodetail-1987259.html
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
const double eps=1e-4;
int n,m;
double a[maxn][maxn],x[maxn];//  a和x分别为方程的左边的矩阵和等式右边的值，求解之后x存的就是结果
int equ,var;//  方程数和未知数个数
int Gauss() {//  返回0表示无解，1表示有解
    int i,j,k,col,max_r;
    for(k=1,col=1; k<=equ&&col<=var; k++,col++) {
        max_r=k;
        for(i=k+1; i<=equ; i++)if(fabs(a[i][col])>fabs(a[max_r][col]))max_r=i;
        if(fabs(a[max_r][col])<eps)return 0;
        if(k!=max_r) {
            for(j=col; j<=var; j++)swap(a[k][j],a[max_r][j]);
            swap(x[k],x[max_r]);
        }
        x[k]/=a[k][col];
        for(j=col+1; j<=var; j++)a[k][j]/=a[k][col];
        a[k][col]=1;
        for(i=0; i<=equ; i++)if(i!=k) {
                x[i]-=x[k]*a[i][k];
                for(j=col+1; j<=var; j++)a[i][j]-=a[k][j]*a[i][col];
                a[i][col]=0;
            }
    }
    return 1;
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Resistance.in","r",stdin);
    scanf("%d%d",&n,&m);
    int from,to;
    double r;
    for(int i=1; i<=m; i++) {
        scanf("%d%d%lf",&from,&to,&r);
        //对于电路中的一条from到to，阻值为r的边。方程组中会有四个项的系数受到影响。
        a[from][from]+=1.0/r,a[to][to]+=1.0/r,a[from][to]-=1.0/r,a[to][from]-=1.0/r;
    }
//  a[n][n]+=1.0;
    x[1]=1.0,x[n]=-1.0;
    /*
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            printf("%.2f ",a[i][j]);
        }
        E;
    }
    */
    equ=var=n;
    Gauss();
    printf("%.2lf ",x[1]-x[n]); //事实上 x[n]等于0恒成立 
//  for(int i=1; i<=n; i++) printf("%.2lf ",x[i]);
    return 0;
}

POJ 3526: The Teacher’s Side of Math
根据每个无理项 $a^{x/m}b^{y/n}$ 的系数和为0（最高项系数和为1）来列方程求解。
题解链接 https://blog.csdn.net/FSAHFGSADHSAKNDAS/article/details/89089005
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
根据每个无理项a^{x/m}b^{y/n}的系数和为0（最高项系数和为1）来列方程求解。
题解链接 https://blog.csdn.net/FSAHFGSADHSAKNDAS/article/details/89089005
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=20+5+5;
const int INF=0x3f3f3f3f;
ll a,m,b,n,C[maxn][maxn];
double G[maxn][maxn];
void getc (int n) {
    for (int i = 0; i <= n; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
}
void init(){
    memset(G,0,sizeof(G));
    int N=n*m;
    for(int i=0;i<=N;i++){
        for(int j=0;j<=i;j++){
            int l=j,r=i-j;
            double temp=C[i][l]*pow(a*1.0,(double)l/m)*pow(b*1.0,(double)r/n);
//          D(temp);E;
            l%=m,r%=n;
            G[l*n+r][i]+=temp;
        }
    }
    G[N][N]=1; //a_nm
    G[N][N+1]=1; //最高项系数和为1 
}
void Gauss (int n) {
    /*
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++)
            printf("%lf ", G[i][j]);
        printf("\n");
    }
    */
    for (int i = 0; i < n; i++) {
        int r = i;
        for (int j = i + 1; j < n; j++)
            if (fabs(G[j][i]) > fabs(G[r][i]))
                r = j;
        if (r != i) {
            for (int j = 0; j <= n; j++)
                swap(G[r][j], G[i][j]);
        }
        if (fabs(G[i][i]) < 1e-9)
            continue;
        for (int k = i + 1; k < n; k++) {
            double f = G[k][i] / G[i][i];
            for (int j = 0; j <= n; j++)
                G[k][j] -= G[i][j] * f;
        }
    }
    for (int i = n-1; i >= 0; i--) {
        for (int j = i+1; j < n; j++)
            G[i][n] -= G[j][j] * G[i][j];
        G[i][i] = G[i][n] / G[i][i];
        if (fabs(G[i][i]) < 1e-9)
            G[i][i] = 0;
    }
    printf("%.0f", G[n-1][n-1]);
    for (int i = n-2; i >= 0; i--)
        printf(" %.0f", G[i][i]);
    printf("\n");
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("The Teacher’s Side of Math.in","r",stdin);
    getc(maxn-5);
    while(scanf("%lld%lld%lld%lld",&a,&m,&b,&n)!=EOF){
        if(!a&&!b&&!m&&!n) break;
        init();
        Gauss(n*m+1);   
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

计数

POJ 2407: Relatives
欧拉函数裸题，不再赘述。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
欧拉函数裸题，不再赘述。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000000000+5;
const int INF=0x3f3f3f3f;
int phi(int n){
    int res=n;
    for(int i=2;i<=(int)sqrt((double)n);i++){
        if(n%i==0){
            res=res/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) res=res/n*(n-1);
    return res;
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Relatives.in","r",stdin);
    int n;
    while(cin>>n){
        if(!n) break;
        cout<<phi(n)<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 1286: Necklace of Beads
与POJ2049相仿，不再赘述。
注意考虑s=0的情况，需要输出0，直接跑会RE。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
与POJ2049相仿，不再赘述。 
注意考虑s=0的情况，需要输出0，直接跑会RE。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=32+5;
const int INF=0x3f3f3f3f;
int c=3,s;
ll ans;
void init(){
    ans=0ll;
}
int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}
ll ksm(ll a,ll b){
    ll res=1ll;
    while(b){
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
void solve(){
    init();
    for(int i=0;i<=s-1;i++){ //旋转 每种情况被重复算了n次 
        ll d=(ll)gcd(i,s);
        ll res=ksm((ll)c,d);
//      D(c);D(d);D(res);E;
        ans+=res;
    }
    //翻转 每种情况被重复计算了n次 
    if(s&1) ans+=(ll)s*ksm((ll)c,(ll)s/2+1); 
    //s为奇数 对称轴穿过一个顶点和一条边，顶点选法有s种，剩余每对点颜色一样 
    //因此穿过对称轴的点颜色有c种，剩余s/2对点，选法有c^(s/2)种 
    else ans+=(ll)s/2*ksm((ll)c,(ll)s/2)+(ll)s/2*ksm((ll)c,(ll)s/2+1); 
    //s为偶数 分两种情况 
    //1 对称轴穿过两条边，边的选法有s/2种，顶点颜色选法c^(s/2)种
    //2 对称轴穿过两个点，点的选法有s/2种，顶点颜色选法c^(s/2-1+2)种（+2是作为对称轴的两个顶点） 
    cout<<ans/(2*s)<<endl;  //总体上 每种情况被重复算了2n次 
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Necklace of Beads.in","r",stdin);
    while(cin>>s){
        if(s==-1) break;
        if(s==0){
            cout<<0<<endl;
            continue;
        }
        solve();
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 2409: Let it Bead
书上原题，需要额外考虑翻转的情况。
题解链接 http://hzwer.com/6861.html
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
书上原题，需要额外考虑翻转的情况。
题解链接 http://hzwer.com/6861.html 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=32+5;
const int INF=0x3f3f3f3f;
int c,s;
ll ans;
void init(){
    ans=0ll;
}
int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}
ll ksm(ll a,ll b){
    ll res=1ll;
    while(b){
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
void solve(){
    init();
    for(int i=0;i<=s-1;i++){ //旋转 每种情况被重复算了n次 
        ll d=(ll)gcd(i,s);
        ll res=ksm((ll)c,d);
//      D(c);D(d);D(res);E;
        ans+=res;
    }
    //翻转 每种情况被重复计算了n次 
    if(s&1) ans+=(ll)s*ksm((ll)c,(ll)s/2+1); 
    //s为奇数 对称轴穿过一个顶点和一条边，顶点选法有s种，剩余每对点颜色一样 
    //因此穿过对称轴的点颜色有c种，剩余s/2对点，选法有c^(s/2)种 
    else ans+=(ll)s/2*ksm((ll)c,(ll)s/2)+(ll)s/2*ksm((ll)c,(ll)s/2+1); 
    //s为偶数 分两种情况 
    //1 对称轴穿过两条边，边的选法有s/2种，顶点颜色选法c^(s/2)种
    //2 对称轴穿过两个点，点的选法有s/2种，顶点颜色选法c^(s/2-1+2)种（+2是作为对称轴的两个顶点） 
    cout<<ans/(2*s)<<endl;  //总体上 每种情况被重复算了2n次 
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Let it Bead.in","r",stdin);
    while(cin>>c>>s){
        if(!c&&!s) break;
        solve();
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

数论（二）

模运算

矩阵

计数

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读