KeepCode 3 解题报告

题目来源

ID	Origin	Title
Problem A	HDU 4407	Sum
Problem B	POJ 1845	Sumdiv
Problem C	POJ 2480	Longge's problem
Problem D	POJ 1012	Joseph
Problem E	POJ 1082	Calendar Game
Problem F	POJ 1099	Square Ice

Problem A

　　将题目转换下, 我们定义函数 Sum ( 1, N ) 为区间[ 1, N ] 与 P 互质的数的和

　　则 Sum( 1, Y ) - Sum( 1, X-1) 即为区间 [ X, Y ] 与 P 互质的数的和

　　再回到本题

　　　　N = 400000 , M = 1000

　　题目中仅有两种操作, 1为统计区间与P互质数的和, 2为更改 X 位置值为C

　　如果我们只进行 1 操作, 则我们通过定义的 Sum 函数可以很轻松的解决这个问题.

　　因为操作数目 M = 1000, 相对于 N 来讲, 它是很小的, 所以我们可以考虑将操作2 忽视,( 单独来处理对应位置的变化情况 )

　　这样我们就可以简化问题, 通过 Sum 函数来解决这个问题. Sum函数的计算方法如下:

问题: 求区间 [ 1, N ] 与 P 互质的数的和

　　首先设: A 为区间[1,N]与P 互质的数的和

　　　　　　B 为区间[1,N] 所有数的和 ( 等差数列求和 B = (1+N)*N/2 )

　　　　　　C 为区间[1,N]与P 不互质的数的和

　　那么我们知道:

　　　　A = B(全集) - C( A的补集 )

　　明显集合 A 不好求, 我们考虑从侧面来计算. 全

　　集 B 等差数列求解没问题, 至于 A的补集 C 我们可以通过容斥原理来求解:

首先来看容斥原理的表达式:　　

　　　 $A \bigcup B \bigcup C = A + B + C - A \bigcap B - A \bigcap C - B \bigcap C + A \bigcap B \bigcap C$ 　( 核心操作: 加奇减偶 )

　　任意正整数都可以因式分解为如下形式:

　　　　　　 $N = p{_{1}}^{e_{1}} \cdot p{_{2}}^{e_{2}} \cdot \cdot \cdot p_{k}^{e_{k}}$ 其中( p1, p2 ... pk 为质数, ei 为次数 )

　　那么任意 X , 与N 不互质, 则 GCD( N, X ) > 1

　　意味着它们有公共的素因子 (最大公约数为非素数,其也是由素数相乘构成 )

　　定义 F( P ) 为区间 [1, N] 以 P为因子( 不仅仅是质因子) 的数的总和

　　则

　　　 $F(N) = \sum_{i=1}^{ e_{k} } F(p_i) - \sum F(p_i*p_j) + \sum F(p_i*p_j*p_k ) +...+ (-1)^{Cnt}*\sum F(p_i*p_j*..*p_cnt)$

　　对于 N = 400000 以内所有数,因式分解后, 最多不同的素因子不超过10个. 我们可以通过二进制状态枚举素因子组合情况来求 F(X)

　　注意:

　　　　对 P 进行因式分解时, 我们可以通过试除法, 仅需筛选到 $\sqrt{ P }$ 就可以了, 因为之后哪怕有素因子,也只有一个. 不可能出现平方甚至更多次方.

否则会 TLE.

解题代码:

View Code

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<map>
#include<set>
#include<algorithm>
using namespace std;

typedef long long LL;
// 此出用来处理变换的操作
// map用来映射，得到最新的更新情况
set < int > S;
map < int,int > Mp;

const int N = 1010;
const int maxn = 1010;

int n, m;
int prime[maxn],size; //maxn以内素数数量
bool vis[maxn];

void GetPrime()
{    //线性筛选素数
    // 素数筛选只处理到 sqrt(400000) 能大幅度降低处理时间，但分解素因子的时候注意 大于sqrt(400000)素因子的情况 
    memset( vis, 0, sizeof(vis));    
    size = 0; vis[0] = vis[1] = true;
    for(int i = 2; i < maxn; i++)
    {
        if( !vis[i] ) prime[size++] = i;
        for(int j = 0; j < size && prime[j]*i < maxn; j++)
        {
            vis[ prime[j]*i ] = true;
            if( i%prime[j] == 0 ) break;
        }
    }
    //素数数量
    //printf("size = %d\n", size);
}   
inline LL Include( int y, int p ) //使用容斥原理，求 [1,y] 区间与 p 不互素的和
{    
    int num = 0, a[10], t = p;    
    for(int i = 0; i < size && prime[i] <= t; i++)    
    {
        if( t%prime[i] == 0 )
        {
            a[num++] = prime[i];
            while(t%prime[i] == 0) t/=prime[i]; // 因为这里少写了个0，WA了一次。
        }
        if( t == 1 ) break;
    }    
    if( t > 1 ) a[num++] = t; //分解素因子的时候注意 大于sqrt(400000)素因子的情况的处理     
    //注意，把400000以内所有数字预处理会TLE，题目最多1000此op=1，所以每次求一次还快点 

    LL res = 0; // 存储结果，注意数值溢出    
    int mask = (1<<num)-1; //二进制表示对应位置取或不取，枚举组合情况
    for(int i = 1; i <= mask; i++)
    {
        int tot = 0;
        LL d = 1;    
        for(int j = 0; j < num; j++)
        {
            if( i&(1<<j) ) 
            {    tot++; d = d*a[j]; }
        }
        // 等差数列求和计算当前素数组合在区间[1,y]内的倍数的和    
        // 区间[1,y]为d的倍数，一共有y/d个,形成一个差值为d的等差数列        
        LL nn = 1LL*y/d, a1 = d, an = a1 + 1LL*(nn-1)*d;
        LL tmp = (a1+an)*nn/2;        // 等比数列求和
        if( (tot&1) == 0 ) tmp = -tmp; //容斥 加奇减偶
        res += tmp; 
    }
    return res;
}
LL solve( int y, int p ) //计算区间[1,y]内与p互质的数的和
{
    // 互质和sum = [1,y]区间所有数和 - 与p不互质的和
    LL sum = 1LL*(1+y)*y/2 - Include( y, p );
    return sum;
}

int gcd( int a, int b )
{    return (b==0)? a : gcd(b,a%b); }

int main()
{
//    init();
    GetPrime();
    int T;
    scanf("%d", &T);
    while( T-- )
    {
        scanf("%d%d", &n,&m);
        Mp.clear();
        S.clear();
        int op, x, y, p;
        while( m-- )
        {
            scanf("%d", &op);
            if( op == 1 )
            {
                scanf("%d%d%d", &x, &y, &p);
                LL res = solve(y,p) - solve(x-1,p);
                // 再处理区间[x,y]发生变换的    
                for(set<int>::iterator it = S.begin(); it != S.end(); it++ )
                {
                    if( (*it >= x) && (*it <= y) )    
                    {
                        if( gcd( p, *it ) == 1 )  res -= *it; //若s[i]与p互质则需要减去该值    
                        int t = Mp[ *it ];
                        if( gcd(t,p) == 1 ) res += t; //若 t 与p 互质则需加该值
                    }    
                }
                printf("%lld\n", res);
            }
            else{
                scanf("%d%d", &x, &p );
                S.insert(x);
                Mp[x] = p;
            }    
        }
    }
    return 0;
}

Problem B

　　任意正整数都可以因式分解为如下形式:

　　　　　　 $N = p{_{1}}^{e_{1}} \cdot p{_{2}}^{e_{2}} \cdot \cdot \cdot p_{k}^{e_{k}}$ 其中( p1, p2 ... pk 为质数, ei 为次数 )

　　定义函数 F( N ) 为 N 的因子和

　　则 $F( N ) = F( p{_{1}}^{e_{1}} \cdot p{_{2}}^{e_{2}} \cdot \cdot \cdot p_{k}^{e_{k}} )$

　　对于 $F( p{_{i}}^{e_{i}} ) = p{_{i}}^{0} + p{_{i}}^{1} + \cdot \cdot \cdot + p{_{i}}^{e_{i} } = \sum_{j=0}^{ e_{i} } p{_{i}}^{j}$ 　　

　　因为 pi 为质因子, 两两互斥, ( 积性函数性质 $F( x \cdot y ) = F(x) \cdot F(y)$ (x,y)两两互斥 ), 所以

　　 $F( N ) = F( p{_{1}}^{e_{1}} \cdot p{_{2}}^{e_{2}} \cdot \cdot \cdot p_{k}^{e_{k}} ) = F( p{_{1}}^{e_{1}} ) \cdot F( p{_{2}}^{e_{2}} ) \cdot \cdot \cdot F(p_{k}^{e_{k}} )$

　　经过以上分析, 对于本题, 可以得到

　　 $F(A^B) = F( A )^B = F( p{_{1}}^{e_{1}} \cdot p{_{2}}^{e_{2}} \cdot \cdot \cdot p_{k}^{e_{k}} ) ^B = F( p{_{1}}^{e_{1}} )^B \cdot F(p{_{2}}^{e_{2}})^B \cdot \cdot \cdot F(p_{k}^{e_{k}} )^B$

　　 $F( p{_{1}}^{e_{1}} )^B \cdot F(p{_{2}}^{e_{2}})^B \cdot \cdot \cdot F(p_{k}^{e_{k}} )^B = F( p{_{1}}^{e_{1}\cdot B} ) \cdot F(p{_{2}}^{e_{2} \cdot B}) \cdot \cdot \cdot F(p_{k}^{e_{k} \cdot B} )$

　　 $F( p{_{i}}^{e_{i}} ) = p{_{i}}^{0} + p{_{i}}^{1} + \cdot \cdot \cdot + p{_{i}}^{e_{i} } = \sum_{j=0}^{ e_{i} } p{_{i}}^{j} = \frac{p{_{i}}^{0} \cdot( p{_i}^{e_{i}+1} - 1 )}{p_{i}-1}$

　　所以我们可以通过将 A 进行因式分解后, 对素因子单独计算然后相乘就可以了

　　提示:

　　　　1. 对于幂的计算, 使用二分快速幂即可

　　　　2. 对于等比数列求和时, 计算 $\frac{ ( p^x - 1 )}{p-1} Mod. 9901$ 时, 对于除以 ( p-1 ), 我们可以通过求 (p-1) 逆元来避免除法.

但是要注意不可求逆元的特殊情况:

　　　　　　p mod 9901 = 0 时, $F( p_{i}^{x} ) = p_i^0 + p_i^1 + ... + p_i^x = 1 + 0 + ... + 0 = 1$

　　　　　　p mod 9901 = 1 时, $F( p_{i}^{x} ) = p_i^0 + p_i^1 + ... + p_i^x = 1 + 1 + ... + 1 = x+1$

　　　　3. 素数筛选的时候, 我们可以只筛选到 $\sqrt{ 50000000 }$ 即可, 用试除法分解其素因子.

解题代码

View Code

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;
const int N = 10010; //注意，为降低时间，我们筛选到sqrt(50000000)就可以了
const int mod = 9901;

int p[2000], size;
bool vis[N];
void GetPrime()
{
    memset( vis, 0, sizeof(vis));
    size = 0;
    for(int i = 2; i < N; i++)
    {
        if( !vis[i] ) p[size++] = i;
        for(int j = 0; (j<size)&&(p[j]*i<N); j++)
        {
            vis[ p[j]*i ] = true;
            if( i%p[j] == 0 ) break;
        }
    }
//    printf("size = %d\n", size);
}
LL Mul( LL a, LL b )
{//按位模拟乘法，避免溢出
    LL res = 0;
    while( b )
    {
        if( b&1 ) if( (res+=a) >= mod ) res -= mod;
        a <<= 1; if( a >= mod ) a -= mod;
        b >>= 1;
    }
    return res;
}
LL Pow( LL x, LL k )
{ //按位模拟快速幂
    if( k ==  0 ) return 1;
    LL res = Pow( x, k/2 )%mod;
    res = res*res%mod;
    if( k&1 ) res *= x;
    return res;
}
LL ExGcd( LL a, LL b, LL &x, LL &y)
{
    if(b == 0) { x = 1; y = 0; return a; } 
    LL r = ExGcd( b, a%b, x, y );
    LL t = x; x = y; y = t-a/b*y;
    return r;
}
LL Inverse( LL A )
{//求逆元
    LL x, y;
    ExGcd( A, mod, x , y );
    return ((x%mod)+mod)%mod;
}

LL Sum( LL q, LL n )
{//等比数列求和 , 注意特殊情形，不能求逆元
    if( q%mod == 0 ) return 1;
    else if( q%mod == 1 ) return n%mod;
    else
    {
        LL A = (Pow(q%mod,n) - 1 + mod)%mod, B = Inverse( q-1 );     
        LL res = A*B%mod; 
        return res;
    }
}    

LL solve( int A, int B )
{
    int num = 0, a[50], b[50], t = A;
    for(int i = 0; (i < size) && (p[i] <= t) ; i++)
    {
        if( t%p[i] == 0 )
        {
            a[num] = p[i];
            b[num] = 1;
            t /= p[i];    
            while( t%p[i] == 0 )
            {
                t /= p[i];
                b[num]++;
            }
            num++;    
        }
        if( t == 1 ) break;    
    }
    if( t > 1 ) { a[num] = t; b[num]=1; num++; }
 
    LL ans = 1;
    for(int i = 0; i < num; i++)
        ans = ans*Sum( a[i], 1LL*b[i]*B+1 )%mod;//加上p^0项，共b[i]*B+1项    
    return ans;
}
int main()
{
    GetPrime();
    int A, B;
    while( scanf("%d%d", &A, &B) != EOF)
    {
        if( (A == 0) || (A == 1) )
            printf("%d\n", A );    
        else
        {
            LL ans = solve( A, B );    
            printf("%lld\n", ans );    
        }    
    }
    return 0;
}

Problem C

　　欧拉函数 $E( N ) = \prod_{i=1}^{k} ( p_i^{e_{i}} - p_i^{e_{i}-1} )$ 表示区间[1, N] 与N互质的数量个数

　　对于区间[ 1, N ] 其中的任意数 X，如果有

　　　　　　 GCD（ N， X ） = K

　　则等价于 GCD（ $\frac{N}{K}$ ， $\frac{X}{K}$ ） = 1

　　等价于 E（ $\frac{X}{K}$ ）在区间 [ 1, $\frac{X}{K}$ ] 与 $\frac{X}{K}$ 互质的数量个数

　　对于本题, 枚举 N 因子, 仅需枚举到 $\sqrt{N}$ , 注意当 $\sqrt{N}$ * $\sqrt{N}$ = N 时的特殊情况处理

解题代码

View Code

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
using namespace std;

typedef long long LL;
LL eular( LL x )
{
    if( x == 0 ) return 0;
    LL res = 1, t = x;
    for(int i = 2; i <= (int)sqrt(1.*x); i++)
    {
        if( t%i == 0 )
        {
            res *= (i-1);
            t /= i;
            while( t%i == 0 ){ res *= i; t /= i; }
        }
        if(t == 1) break;    
    }
    if(t > 1) res *= (t-1);
    return res;
}

int main()
{
    int n;
    while( scanf("%d", &n ) != EOF)
    {
        LL res = eular(n) + n;
        for(int i = 2; i <= (int)sqrt(n); i++)
        {
            if( n%i == 0 )
            {
                if( i*i == n ) res += eular(i)*i;
                else
                {
                    res += eular( i )* (n/i);
                    res += eular( n/i ) * i;
                }    
            }
        }
        printf("%lld\n", res );    
    }
    return 0;
}

Problem D

　　2K个人围成一圈,分别编号为 1,2,3,...,k,k+1,...,k+k, 前 k 次需要首先 Excute 编号为[ k+1, k+k ] 的 k 个人

　看到题目后一直想用模线性同余方程组搞, 后面弄好了好久,发现没规律可言, 然而K又不大,只接模拟暴力出结果然后打表就OK了.

　　每次 Excute 后减少一人.

　　现在假设数值为M ,则当 k = 6 时, 因为每次的起点s是不同的,我们假定为第i次的地点为 si

　　　　第一次, s1 + M % 2k

　　　　第二次, s2 + M % (2k-1)

　　　　....

　　　　第 k 次, sk + M % (k+1)

　　当然, si 是对 2K 取模, 因为围成了一个圈. 枚举 M 后, 模拟求出 K 次 ExCute的情况, 然后判定是否合理.

解题代码

View Code

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
/*
// 计算结果代码
int main()
{
    int k = 6;
    bool vis[100];
    //while( scanf("%d",&k) != EOF )
    for( k = 1; k <= 13; k++)    
    {
        for(int m = 1; ; m++)
        {
            int s = 0, C = k+k;
            memset( vis , 0, sizeof(vis) );    
            for(int i = k+k; i > k; i-- )
            {
                int r = m%i, cnt = 1;
                while( (cnt%i) != r )
                {
                    s = (s+1)%C;    
                    if( !vis[s] ) cnt++;    
                }
                vis[s] = true;    
                s = (s+1)%C;
                while( vis[s] ) s = (s+1)%C;
            }
            bool flag= true;    
            for(int i = k; i < k+k; i++)
                if( !vis[i] ) flag = false;
            if(flag) {    printf("k = %d, m = %d\n", k, m); break; }
        }
    }
    return 0;
}
*/
int ans[15] = {0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881};
int main()
{
    int k;
    while( scanf("%d",&k) ,k )
        printf("%d\n", ans[k] );
    return 0;
}