A

/*Huyyt*/#include
      
       #define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long ll;typedef unsigned long long ull;const int dir[8][2] = {
    {
    0, 1}, {
    1, 0}, {
    0, -1}, { -1, 0}, {
    1, 1}, {
    1, -1}, { -1, -1}, { -1, 1}};const int mod = 1e9 + 7, gakki = 5 + 2 + 1 + 19880611 + 1e9;const int MAXN = 2e5 + 5, MAXM = 2e5 + 5, N = 2e5 + 5;const int MAXQ = 100010;/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;inline void addedge(int u, int v){        to[++tot] = v;        nxt[tot] = Head[u];        Head[u] = tot;}*/inline void read(int &v){        v = 0;        char c = 0;        int p = 1;        while (c < '0' || c > '9')        {                if (c == '-')                {                        p = -1;                }                c = getchar();        }        while (c >= '0' && c <= '9')        {                v = (v << 3) + (v << 1) + c - '0';                c = getchar();        }        v *= p;}map
       
         mp;int main(){        int n;        read(n);        int ans = 0;        mp[0] = 1;        for (int i = 1; i <= n; i++)        {                int now;                read(now);                if (!mp[now])                {                        mp[now] = 1;                        ans++;                }        }        cout << ans << endl;        return 0;}
       
      

B

题意:

给你L,R,A,B四个数 要你找出一对在L,R范围内的数使得他们的GCD为A,LCM为B 问你有几对

解:

假设我们找到的数是X,Y 那么X*Y肯定为LCM*GCD 因为LCM=X*Y/GCD

所以我们只要在1~sqrt(LCM*GCD)范围内枚举数即可 但是LCM*GCD的最大值是1e18 平方根下来是1e9还是不行

我们观察到X,Y的GCD是X 那么就说明X,Y都是GCD的倍数 所以我们不用++枚举 直接+X枚举即可

这样的复杂度是sqrt(LCM*GCD)/GCD=sqrt(LCM/GCD)  LCM/GCD最大是1e9 可以接受

/*Huyyt*/#include
      
       #define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long ll;typedef unsigned long long ull;const int dir[8][2] = {
    {
    0, 1}, {
    1, 0}, {
    0, -1}, { -1, 0}, {
    1, 1}, {
    1, -1}, { -1, -1}, { -1, 1}};const int mod = 1e9 + 7, gakki = 5 + 2 + 1 + 19880611 + 1e9;const int MAXN = 2e5 + 5, MAXM = 2e5 + 5, N = 2e5 + 5;const int MAXQ = 100010;/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;inline void addedge(int u, int v){        to[++tot] = v;        nxt[tot] = Head[u];        Head[u] = tot;}*/inline void read(int &v){        v = 0;        char c = 0;        int p = 1;        while (c < '0' || c > '9')        {                if (c == '-')                {                        p = -1;                }                c = getchar();        }        while (c >= '0' && c <= '9')        {                v = (v << 3) + (v << 1) + c - '0';                c = getchar();        }        v *= p;}ll gcd(ll a, ll b){        ll t;        while (b)        {                t = b;                b = a % b;                a = t;        }        return a;}int main(){        ll l, r, x, y;        cin >> l >> r >> x >> y;        ll rl = l;        ll sum = x * y;        ll ans = 0;        ll a, b;        if (l % x != 0)        {                l = (l / x + 1) * x;        }        for (ll i = l; i <= sqrt(sum) && i <= r; i += x)        {                if (sum % i == 0)                {                        a = i, b = sum / i;                        if (b >= rl && b <= r)                        {                                if (gcd(a, b) == x)                                {                                        if (a == b)                                        {                                                ans++;                                        }                                        else                                        {                                                ans += 2;                                        }                                        //cout << a << " " << b << endl;                                }                        }                }        }        cout << ans << endl;        return 0;}
      

C

题意:

你开始有X个裙子 你有K+1次增长机会 前K次会100%的增长一倍 但是增长后有50%的机会会减少一个

给你X,K(1e18) 问你最后裙子数量的期望值是多少(mod 1e9+7)

解:

纯推公式找规律题

我们很容易知道其实在K月之后(总共有K+1月)最后可能得到的裙子数是连续的

即如果刚开始有X个裙子且K=2时 他经过K月(没经过最后特殊的那一月)后可能得到的为 4*X,4*X-1,4*X-2,4*X-3 这四种答案

所以可以得到公式经过K月后的期望值为 (2^k*X+2^k*X-2^k+1)*2^k/2/2^k=(2^k+1*X-2^k+1)/2

这是K月后的期望值 还有最后一月要*2 所以直接*2 最后的答案即为2^k+1*X-2^k+1

/*Huyyt*/#include
      
       #define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long ll;typedef unsigned long long ull;const int dir[8][2] = {
    {
    0, 1}, {
    1, 0}, {
    0, -1}, { -1, 0}, {
    1, 1}, {
    1, -1}, { -1, -1}, { -1, 1}};const int mod = 1e9 + 7, gakki = 5 + 2 + 1 + 19880611 + 1e9;const int MAXN = 2e5 + 5, MAXM = 2e5 + 5, N = 2e5 + 5;const int MAXQ = 100010;/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;inline void addedge(int u, int v){        to[++tot] = v;        nxt[tot] = Head[u];        Head[u] = tot;}*/inline void read(int &v){        v = 0;        char c = 0;        int p = 1;        while (c < '0' || c > '9')        {                if (c == '-')                {                        p = -1;                }                c = getchar();        }        while (c >= '0' && c <= '9')        {                v = (v << 3) + (v << 1) + c - '0';                c = getchar();        }        v *= p;}ll Qpow(ll a, ll b){        ll ans = 1, base = a;        while (b != 0)        {                if (b & 1 != 0)                {                        ans *= base;                        ans %= mod;                }                base *= base;                base %= mod;                b >>= 1LL;        }        return ans;}int main(){        ll x, k;        cin >> x >> k;        if (x == 0)        {                cout << 0 << endl;                return 0;        }        ll ans1 = Qpow(2, k + 1);        x %= mod;        ans1 = (ans1 * x) % mod;        ll ans2 = (Qpow(2, k) - 1 + mod) % mod;        cout << (ans1 - ans2 + mod) % mod << endl;        return 0;}
      

D