程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu1695(莫比烏斯)或歐拉函數+容斥

hdu1695(莫比烏斯)或歐拉函數+容斥

編輯：C++入門知識

hdu1695(莫比烏斯)或歐拉函數+容斥

題意：求1-b和1-d之內各選一個數組成數對，問最大公約數為k的數對有多少個，數對是有序的。(b,d,k<=100000)

解法1：這個可以簡化成1-b/k 和1-d/k 的互質有序數對的個數。假設b=b/k，d=d/k,b<=d.歐拉函數可以算出1-b與1-b之內的互質對數，然後在b+1到d的數i，求每個i在1-b之間有多少互質的數。解法是容斥，getans函數參數的意義：1-tool中含有rem位置之後的i的質因子的數的個數。

在

for(int j=rem;j<=factor[i][0];j++)
    ans+=tool/factor[i][j]-getnum(i,tool/factor[i][j],j+1);

這個循環中，ans加的等號後每項表示當前最大的質因子是factor[i][j]的數量，目的是去重。

解法2：莫比烏斯，莫比烏斯數組確實很有用。其實也很簡單，mou的位置的含義是，首先如果i有個質因子出現2次或以上，則mou值為0，否則1與-1跟i的質因子奇偶性決定。目的也是容斥。

解法1代碼：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
#define zero(_) (abs(_)<=eps)
const double pi=acos(-1.0);
typedef long long LL;
const int Max=100010;
const LL INF=0x3FFFFFFF;
int a, b, c, d, k;
int factor[Max][20];
bool rem[Max];
LL oular[Max];
void init()
{
    for(int i=1; i>t;
    init();int kk=1;
    while(t--)
    {
        cin>>a>>b>>c>>d>>k;
        printf("Case %d: ",kk++);
        if(k==0)
        {
            cout<<"0\n";
            continue;
        }
        b/=k;
        d/=k;
        if(b>d)swap(b,d);
        LL ans=oular[b];
        for(int i=b+1;i<=d;i++)
        {
            ans+=b-getnum(i,b,1);
        }
        cout<解法2代碼：/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
#define zero(_) (abs(_)<=eps)
const double pi=acos(-1.0);
typedef long long LL;
const int Max=100010;
const LL INF=0x3FFFFFFF;
int a, b, c, d, k;
bool rem[Max];
int mou[Max];
void init()
{
    mou[1]=1;
    for(LL i=2; i>t;
    init();
    int kk=1;
    while(t--)
    {
        cin>>a>>b>>c>>d>>k;
        printf("Case %d: ",kk++);
        if(k==0)
        {
            cout<<"0\n";
            continue;
        }
        b/=k;
        d/=k;
        if(b > d)swap(b,d);
        long long ans1 = 0;
        for(int i = 1; i <= b; i++)
            ans1 += (long long)mou[i]*(b/i)*(d/i);
        long long ans2 = 0;
        for(int i = 1; i <= b; i++)
            ans2 += (long long)mou[i]*(b/i)*(b/i);
        ans1 -= ans2/2;
        cout<