程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 4407 Sum(容斥)

hdu 4407 Sum(容斥)

編輯：C++入門知識

hdu 4407 Sum(容斥)

http://acm.hdu.edu.cn/showproblem.php?pid=4407

起初有n個數1~n，這裡有m個操作，兩種類型。操作1：求出[x,y]區間內與p互質的數的和。操作2：將第x位置的數變成y。對於每一個詢問，輸出結果。

因為只有1000次操作，而且起初是有序的。那麼對於第i個詢問，我們先忽略i之前的所有的第2種操作，即認為n個數為1~n，根據容斥原理求出[x,y]區間內與p互質的數之和，然後遍歷i之前的操作2，對所求的答案進行調整即可。wa了無數次，改了好久，是因為我忽略的一點，對x位置的數有可能進行多次修改，我們只需考慮最後一次修改即可。所以可用用map保存一下操作2。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL __int64
//#define LL long long
#define eps 1e-9
#define PI acos(-1.0)
using namespace std;

const int maxn = 400010;

int n,m;
bool flag[maxn];
int prime[maxn];
int fac[100];
int facCnt;
LL ans;
mapM;

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

void getPrime()
{
    memset(flag,false,sizeof(flag));
    prime[0] = 0;
    for(int i = 2; i < maxn; i++)
    {
        if(flag[i] == false)
            prime[++prime[0]] = i;
        for(int j = 1; j <= prime[0]&&prime[j]*i < maxn; j++)
        {
            flag[prime[j]*i] = true;
            if(i % prime[j] == 0)
                break;
        }
    }
}

void getFac(int num)
{
    int tmp = num;
    facCnt = 0;
    for(int i = 1; i <= prime[0]&&prime[i]*prime[i] <= tmp; i++)
    {
        if(tmp % prime[i] == 0)
        {
            fac[facCnt++] = prime[i];
            while(tmp % prime[i] == 0)
                tmp /= prime[i];
        }
        if(tmp == 1)
            break;
    }
    if(tmp > 1)
        fac[facCnt++] = tmp;
}

LL getSum(int t)
{
    return ((1 + 1LL * t) * 1LL * t) >> 1;
}

//求【1，r】內與該數互質的數之和。
LL cal(int r)
{
    LL anw = getSum(r);
    LL tmp = 0;

    for(int i = 1; i < (1<::iterator it;
                for(it = M.begin(); it != M.end(); it++)
                {
                   if(it->first >= x && it->first <= y)
                   {
                        if(gcd(z,it->first) == 1)
                            ans -= it->first;
                        if(gcd(z,it->second) == 1)
                            ans += it->second;
                   }
                }
                printf("%I64d\n",ans);
            }
            else
            {
                scanf("%d %d",&x,&y);
                M[x] = y;
            }
        }
    }
    return 0;
}