亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

歐拉函數+容斥原理

系統 2084 0

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

      
         1
      
      
        /*
      
      
        *


      
      
         2
      
      
             GCD(x,y)=k;在x小于b且y小于d時有多少組答案


      
      
         3
      
      
        2


      
      
         4
      
      
        1 3 1 5 1


      
      
         5
      
      
        1 11014 1 14409 9


      
      
         6
      
      
         7
      
      
        Case 1: 9


      
      
         8
      
      
        Case 2: 736427


      
      
         9
      
      
        10
      
      
        For the first sample input, all the 9 pairs of numbers are 


      
      
        11
      
      
        (1,1),(1,2),(1,3),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5).


      
      
        12
      
      
        *
      
      
        */
      
      
        13
      
       #include <iostream>


      
        14
      
       #include <cstdio>


      
        15
      
       #include <vector>


      
        16
      
       #include <cmath>


      
        17
      
      
        using
      
      
        namespace
      
      
         std;


      
      
        18
      
      
        const
      
      
        int
      
       Ni = 
      
        100010
      
      
        ;


      
      
        19
      
      
        int
      
      
         phi[Ni];


      
      
        20
      
       vector<
      
        int
      
      >
      
         prime[Ni];


      
      
        21
      
      
        long
      
      
        long
      
      
         sphi[Ni];


      
      
        22
      
      
        void
      
       phi_table(
      
        int
      
      
         n)


      
      
        23
      
      
        {


      
      
        24
      
           phi[
      
        1
      
      ]=
      
        1
      
      
        ;


      
      
        25
      
      
        for
      
      (
      
        int
      
       i=
      
        2
      
      ;i<=n;i++) 
      
        if
      
      (!
      
        phi[i])


      
      
        26
      
      
            {


      
      
        27
      
      
        for
      
      (
      
        int
      
       j=i;j<=n;j+=
      
        i)


      
      
        28
      
      
                {


      
      
        29
      
      
        if
      
      (!(phi[j])) phi[j]=
      
        j;


      
      
        30
      
      
                    prime[j].push_back(i);


      
      
        31
      
                   phi[j]-=phi[j]/
      
        i;


      
      
        32
      
      
                }


      
      
        33
      
      
            }


      
      
        34
      
           sphi[
      
        0
      
      ]=
      
        0
      
      
        ;


      
      
        35
      
      
        for
      
      (
      
        int
      
       i=
      
        1
      
      ;i<=n;i++
      
        )


      
      
        36
      
      
            {


      
      
        37
      
               sphi[i]=sphi[i-
      
        1
      
      ]+
      
        phi[i];


      
      
        38
      
      
            }


      
      
        39
      
      
        }


      
      
        40
      
      
        int
      
       dfs(
      
        int
      
       x,
      
        int
      
       b,
      
        int
      
       k) 
      
        ///
      
      
        求0到b中,與k不互質的個數,x為k的第x個質數因子
      
      
        41
      
       {
      
        //
      
      
        容斥定理
      
      
        42
      
      
        int
      
       res=
      
        0
      
      
        ;


      
      
        43
      
      
        for
      
      (
      
        int
      
       i=x;i<prime[k].size();i++
      
        )


      
      
        44
      
               res+=b/prime[k][i]-dfs(i+
      
        1
      
      ,b/
      
        prime[k][i],k);


      
      
        45
      
      
        return
      
      
         res;


      
      
        46
      
      
        }


      
      
        47
      
      
        int
      
      
         main()


      
      
        48
      
      
        {


      
      
        49
      
      
        int
      
      
         t,i;


      
      
        50
      
      
        int
      
       a,b,c,d,k,cs=
      
        1
      
      
        ;


      
      
        51
      
           phi_table(
      
        100005
      
      
        );


      
      
        52
      
           scanf(
      
        "
      
      
        %d
      
      
        "
      
      ,&
      
        t);


      
      
        53
      
      
        for
      
      (cs=
      
        1
      
      ;cs<=t;cs++
      
        )


      
      
        54
      
      
            {


      
      
        55
      
               scanf(
      
        "
      
      
        %d%d%d%d%d
      
      
        "
      
      ,&a,&b,&c,&d,&
      
        k);


      
      
        56
      
      
        if
      
      (k==
      
        0
      
      ) {printf(
      
        "
      
      
        Case %d: 0\n
      
      
        "
      
      ,cs);
      
        continue
      
      
        ;}


      
      
        57
      
      
        58
      
               b/=k;d/=
      
        k;


      
      
        59
      
      
        if
      
      (b>
      
        d) swap(b,d);


      
      
        60
      
      
        long
      
      
        long
      
       ans=
      
        sphi[b];


      
      
        61
      
      
        for
      
      (i=b+
      
        1
      
      ;i<=d;i++
      
        )


      
      
        62
      
      
                {


      
      
        63
      
                   ans+=b-dfs(
      
        0
      
      
        ,b,i);


      
      
        64
      
      
                }


      
      
        65
      
               printf(
      
        "
      
      
        Case %d: %I64d\n
      
      
        "
      
      
        ,cs,ans);


      
      
        66
      
      
            }


      
      
        67
      
      
        return
      
      
        0
      
      
        ;


      
      
        68
      
       }
    

?

歐拉函數+容斥原理


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 免费福利视频网站 | 99国产精品免费观看视频 | 亚洲综合在线播放 | 欧美性久久久久 | 曰本还a大片免费无播放器 曰本黄色录像 | 日本免费不卡视频一区二区三区 | 夜夜爽夜夜 | 亚洲精品区在线播放一区二区 | 91社区视频 | 色狠狠狠色噜噜噜综合网 | 久久久久久一级毛片免费无遮挡 | 国产精品成人观看视频网站 | 99久久国产综合精品网成人影院 | 久久免 | 第一序列番外篇在哪里看 | 色 综合 欧美 亚洲 国产 | 在线黄色免费 | 久久成人免费大片 | 国产高清自拍 | 久久综合九色 | 久久精品综合国产二区 | 九九热免费观看 | 天天摸天天碰色综合网 | 国产性大片黄在线观看在线放 | 日本高清视频一区二区三区 | 国产女人水多毛片18 | 国产精品视频久久久 | 久久久久久久九九九九 | riav久久中文一区二区 | 亚洲国产精品乱码一区二区三区 | 俺去鲁婷婷六月色综合 | 视频三区精品中文字幕 | www.亚洲一区二区三区 | 欧美肥婆xxxx欧美另类 | 午夜免费体验 | 亚洲一区二区三区视频 | 99国产在线播放 | 欧美伊人久久久久久久久影院 | 免看一级一片一在线看 | 国产日产亚洲精品 | 久久综合给会久久狠狠狠 |