一些数学题目

https://vjudge.net/contest/167937#overview

UVA10006

给你一个数判断是不是 rmichael 数定义是能通过a ^n %n =a 但是不是素数

快速幂好像一定要深搜的普通的超时了

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

typedef long long LL;

int prime[65000];

LL powmod( int a, int n, int m )
{
    if ( n == 1 ) return a%m;
    LL x = powmod( a, n/2, m );
    x = (x*x)%m;
    if ( n%2 ) x = (x*a)%m;
    return x;
}

int tests( int n )
{
    for ( int i = 2 ; i < n ; ++ i )
        if ( powmod( i, n, n ) != i )
            return 0;
    return 1;
}

int main()
{
    //打表计算素数
    for ( int i = 0 ; i < 65000 ; ++ i )
        prime[i] = 1;
    for ( int i = 2 ; i < 65000 ; ++ i )
        if ( prime[i] )
            for ( int j = 2*i ; j < 65000 ; j += i )
                prime[j] = 0;
    
    int n;
    while ( cin >> n && n )
        if ( !prime[n] && tests( n ) )
            cout << "The number " << n << " is a Carmichael number.
";
        else cout << n << " is normal.
";
    
    return 0;
}

View Code

POJ 3421

X-factor Chains

给你一个数a 让你求他的因子 1 x1 x2 xn a

并且x1|1 x2|x1 ... a|xn

求最大长度最大长度有多少种可能

100

2 2 5 5

1 2 4 25 100

就是因子长度就行

先素因子分解然后全排列 /平均分配的

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<queue>
#include<set>
#include<map>

using namespace std;

#define ll long long
#define inf  1e15+7
#define MAXN 1000010
#define exp 1e-4

int z[50];
int cn[50];

ll f(int a)
{
    ll ans=1;
    for(int i=1;i<=a;i++)
        ans=ans*i;
    return ans;
}
int main()
{

    int n;
    while(scanf("%d",&n)!=EOF)
    {
        double en=sqrt(n);
        int cnt=0;
        memset(cn,0,sizeof(cn));
        int b=n;
        for(int i=2;i<=en;i++)
        {
            if(b%i==0)
            {
                z[cnt]=i;
                while(b%i==0)
                {
                    b=b/i;
                    cn[cnt]++;
                }
                cnt++;
            }
        }
        if(b>1)
        {
            z[cnt]=b;
            cn[cnt++]=1;
        }
        int sum=0;
        for(int i=0;i<cnt;i++)
            sum+=cn[i];
        ll ans=f(sum);
        for(int i=0;i<cnt;i++)
            ans=ans/f(cn[i]);
        printf("%d %lld
",sum,ans);
    }
    return 0;
}

View Code