7月11日

A.

set|set.in|set.out

题目描述：

维护一个可重集，支持：

插入一个正整数

询问一个正整数k，集合中有多少个数是k的倍数

输入格式：

第一行一个整数N，表示操作数量。

接下来N行，每行两个整数a,b

如果a=1，表示向集合插入一个数b

如果a=2，询问有多少个数是b的倍数

输出格式：

输出一行一个整数，表示所有询问的答案的亦或和（不要想多，只是防cena智障）

样例输入：

5

1 2

1 3

2 2

1 6

2 3

样例输出：

3

数据范围：

共40组数据

对于第i组数据，n==1000*i，所有的b<=n

每组数据时限0.5秒

#include<cstdio>

#include<iostream>

#include<cstring>

#define PROC "set"

#define LL long long

using namespace std;

const int MAXN = 40 * 1000+5;

LL ans,now[MAXN]; int n;

void deal(int x)

{   

        int i;

        for (i = 1;i*i<x;i++)

        {

               if (x % i ==0)

                {

                now[i]++;now[x/i]++;

                }

        }

        if (i*i==x) now[i]++; return;

}

int main()

{

        scanf("%d",&n);

        int a,b;

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

        {

               scanf("%d%d",&a,&b);

            if (a==1)

            deal(b);

            else ans^=now[b];

        }

    cout<<ans;

        return 0;

}

1.正解：即做。

做：普通思路显然超时，故转换思维，公约数以计，5分钟AC。

改：难得不用改。

得：简单复杂度计算方式 如此题：n * n^0.5

B.未完待续

C．loop|loop.in|loop.out

题目描述：

有N个点。

现在重复这样的操作：

随机找一个出度为0的点p1，随机找一个入度为0的点p2，连一条有向边从p1指向p2。直到没有出度为0的点。

统计最终状态这个图中的环的期望个数。

为了保证答案精度，提供另外一个参数W（正整数），请你输出小于你的答案乘上W后的最大整数。

输入格式：

一行两个整数N，W。

输出格式：

一行一个整数（保证不超过10^6）。

样例输入（多组，测试数据中只有一组）：

1 100

2 100

样例输出：

99

149

数据范围：

30%  N<=100

70%  N<=5*10^6

100%  N<=10^18

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

#define PROC "loop"

using namespace std;

const double eps = 0.00000001;

long long  n,w;

double ans = 0.0;

int main()

{

        cin>>n>>w;

        if (n<5000000)

        {

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

                ans +=1.0/(double) i;

        }

        else ans = log(n) + 0.57721566490;

        cout<<(int)floor(ans  * w - eps);

        return 0;

}

3.正解：数学期望得公式（1/1+1/2+……+1/n），以欧拉函数优化n->正无穷值

   即 ans = ln n + 欧拉常数（推导过程未知）

   求欧拉常数技巧，暴力至极大值，减去ln n即可。

做：已推出公式，由于数学期望认识有误，故舍去，以自法求得n=3 answer，找规律解之。

改：double转化ｉ +　eps取 floor

得：变量类型毁一生