Codeforces Round 525 (Div. 2)

Diposting di 2019-04-24 | Edited on 2018-12-05

A. Ehab and another construction problem(水题，暴力)

题解

虽然是水题但是我还是要讲一下，这个题目的范围一看就知道暴力一下就可以求出答案，但是我一开始看到这题的时候确实懵逼了一会，感觉这题有很明显的规律，后来看了别人的代码终于发现了，就是除了1之外，其他任意的数x都可以用x表示a和b 完美符合条件，这样复杂度只要O（1）而且暴力就过不去了。

int x;
cin>>x;
if(x==1)cout<<-1<<endl;
else cout<<x<<" "<<x<<endl;

B.Ehab and subtraction (排序，优先队列)

priority_queue<int,vector<int>,greater<int> >pq;
int main()
{
    int n,k;
    cin>>n>>k;
    while(n--){
        int a;
        cin>>a;
        pq.push(a);
    }
    int num=0;
    while(k--){
        if(pq.empty())cout<<0<<endl;
        else{
            int sum=pq.top();pq.pop();
            while(!pq.empty()&&pq.top()==sum)pq.pop();
            if(sum-num<=0)cout<<0<<endl;
            else cout<<sum-num<<endl;
            num=sum;
        }
    }
    return 0;
}

C.Ehab and a 2-operation task (思维)

题意

给定一个长度为 n 的数组a[ ]，并且有两种操作：

　　①将前 i 个数全都加上 x;

　　②将前 i 个数全都 mod x

　　要求用不超过 n+1 次操作，使得数组 a[ ] 严格单调递增。

题解

注意mod可以把一个大的数变成一个我们想要的一个数（前提，这个数必须比我们想要的那个数大很多)

可以把n 个数全部加上一个超级大的值,然后取模强行组成为递增的数组即可。

int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
cout<<n+1<<endl;
cout<<"1 "<<n<<" 100000"<<endl;
for(int i=1;i<=n;i++){
    cout<<2<<" "<<i<<" "<<(100000+a[i]-(i-1))<<endl;
    //cout<<(100000+a[i])%(100000+a[i]-(i-1))<<endl;
}

D.Ehab and another another xor problem (思维,位运算)

题意

系统中有两个数(a,b)，请使用62以内次询问来确定出(a,b)

每次可以询问两个数(c,d)

若a⊕c>b⊕da⊕c>b⊕d返回11

若a⊕c=b⊕da⊕c=b⊕d返回00

若a⊕c<b⊕da⊕c<b⊕d返回−1−1

保证/需要保证0⩽a,b,c,d,<2^30

题解

我是，先判断一下a,b
然后a如果大于b
判断是不是因为多了最高位
然后a和b都亦或最高位
如果a小于说明是最高位起作用了同时不能确定后面的小位谁大谁小
如果a还是大于说明是相同的然后把a亦或一个1 (相当于把1去掉)如果小于就说明原本都是1 不然就是0 同时这样可以知道a还是比b大
然后b大于a同理
等于就判断是0还是1
这样每一位都判断两次，应该是30*2

#include<bits/stdc++.h>
using namespace std;
int a,b;
int top=29;
int who=0;
void run();
void getmax(){
    if(top<0)return;
    cout<<"? "<<a<<" "<<b<<endl;
    fflush(stdout);
    cin>>who;
    run();

}
/*
1000011
1000111
*/
void run(){
    if(top<0)return;
    if(who==1){
        cout<<"? "<<(a|(1<<top))<<" "<<(b|(1<<top))<<endl;
        fflush(stdout);
        cin>>who;
        if(who==-1)a|=(1<<top),top--,getmax();
        else{
            cout<<"? "<<(a|(1<<top))<<" "<<b<<endl;
            fflush(stdout);
            cin>>who;
            if(who==-1)a|=(1<<top),b|=(1<<top),top--,who=1,run();
            else top--,who=1,run();
        }
        return;
    }
    else if(who==-1){
        cout<<"? "<<(a|(1<<top))<<" "<<(b|(1<<top))<<endl;
        fflush(stdout);
        cin>>who;
        if(who==1)b|=(1<<top),top--,getmax();
        else{
            cout<<"? "<<a<<" "<<(b|(1<<top))<<endl;
            fflush(stdout);
            cin>>who;
            if(who==1)a|=(1<<top),b|=(1<<top),top--,who=-1,run();
            else top--,who=-1,run();
        }
        return;
    }
    else{
        cout<<"? "<<(a|(1<<top))<<" "<<b<<endl;
        fflush(stdout);
        cin>>who;
        if(who==-1)a|=(1<<top),b|=(1<<top),top--,getmax();
        else top--,getmax();
    }
}
int main(){
    getmax();
    cout<<"! "<<a<<" "<<b<<endl;
    fflush(stdout);
    return 0;
}

E.Ehab and a component choosing problem (树形DP，贪心)

题意

给出一棵树，每个节点有权值，选出k个联通块，最大化

$\frac{\sum_{i \in S} a_i}{k}$

题解

结论：选出的kk个联通块的大小是一样的且都等于最大联通块的大小(参考博客https://www.cnblogs.com/zwfymqz/p/10069374.html)

证明：因为我们是在保证分数最大的情况下才去最大化k，一个很经典的结论是单独选择一个权值最大的联通块得到的分数一定是最大的，然后我们这时我们才去考虑最大化k

那么思路就很清晰了，先一遍dfs dp出最大联通块，然后再一遍dfs从下往上删就行了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
vector<int>ve[maxn];
ll value[maxn];
ll dp[maxn];
ll dp2[maxn];
void add(int x,int y){
    ve[x].push_back(y);
    ve[y].push_back(x);
}
ll ans=-inf;
void dfs(int now,int pre){
    dp[now]=value[now]*1LL;
    int sz=ve[now].size();
    for(auto i:ve[now]){
        if(i==pre)continue;
        dfs(i,now);
        dp[now]=max(dp[now],dp[now]+dp[i]);
    }
    ans=max(ans,dp[now]);
}
ll num;
void dfs1(int now,int pre){
    dp2[now]=value[now]*1LL;
    int sz=ve[now].size();
    for(auto i:ve[now]){
        if(i==pre)continue;
        dfs1(i,now);
        dp2[now]=max(dp2[now],dp2[now]+dp2[i]);
    }
    if(dp2[now]==ans)num++,dp2[now]=0;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>value[i];
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    dfs(1,0);dfs1(1,0);
    cout<<1LL*ans*num<<" "<<num<<endl;
    return 0;
}

Codeforces Round 272(Div. 2)

Diposting di 2019-04-24 | Edited on 2019-03-31

传送门

A - Dreamoon and Stairs (暴力枚举两步的数量)

B - Dreamoon and WiFi (dfs)

思路

因为长度只有十所以直接暴力dfs选择,复杂度$2^{10}$

C - Dreamoon and Sums (公式)

思路

$\frac{div(x,b)}{mod(x,b)}=k\\ \to div(x,b)=k \times mod(x,b)\\ \to x=k \times mod(x,b)\times b+mod(x,b) \\\to x= mod(x,b)(k\times b+1)$

然后因为$b,$已知$mod(x,b)$在$0->b-1$之间 $k$在$1->a$之间

D - Dreamoon and Sets (找规律)

思路

发现需要满足条件需要最近的四个互质的数枚举发现1,2,3,5符合

下一组应该是7,8,9,11,

13,14,15,17

以此类推

E - Dreamoon and String (Dp)

思路

$dp[i][j]表示前i个删除了j个的最优值$

$dp[i][j]=dp[i-1][j] 不删除$

$dp[i][j]=dp[i-1][j-1]删除了自己$

$dp[i][j]=dp[i-ned-lenb][j-ned]删除了一些$

Codeforces Round 271(Div. 2)

Diposting di 2019-04-24 | Edited on 2019-03-29

传送门

C.Captain Marmot (几何,点旋转)

思路

其中顺时针旋转为负，逆时针旋转为正，角度angle是弧度值，如旋转30度转换为弧度为： $angle = pi/180 * 30$。

4、度与角度的转换
根据圆为$360 º$，弧度为$2π$，即 $360º = 2π$

4.1 角度转弧度：$2π / 360 = π / 180 ≈ 0.0174rad$, 即: $度数 (π / 180） = 弧度$
例如：将30º转为弧度rad
$ 30º (π / 180）= 0.523320 rad $

4.2 弧度转角度: $360 / 2π = 180 / π ≈ 57.3º$, 即: $ 弧度 (180 / π） = 度数$
例如：将$0.523320rad$转为度º
$0.523320rad (180 / π) = 29.9992352688º $

若o不是原点，则可先将a点坐标转换为相对坐标计算，计算结果再加上o点坐标。

参与计算的a点坐标实际应为 a - 0,最终计算公式如下：

$b.x = ( a.x - o.x)cos(angle) - (a.y - o.y)sin(angle) + o.x$

$b.y = (a.x - o.x)sin(angle) + (a.y - o.y)cos(angle) + o.y$

Flowers (DP)

思路

少于k的肯定全是1因为都只能放红色。

大于K的可以放红色$dp[i-1]$ 或者连续的k个白色$dp[i-k]$

E - Pillars (DP+线段树+离散化)

思路

很明显的DP，但是数值太大，所以考虑离散化然线段树取区间最大值

F - Ant colony (线段树区间gcd,线段树求最小值的个数)

思路

题意就是查询区间GCD 然后求出区间gcd的个数，后面的操作也可以主席树写

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
int a[maxn];
#define bug cout<<"here"<<endl;
struct Tree{
    #define ls (o<<1)
    #define rs ((o<<1)|1)
    int gcd[maxn<<2],mi[maxn<<2],num[maxn<<2];
    void push_up(int o){
        gcd[o]=__gcd(gcd[ls],gcd[rs]);
    }
    void build(int o,int l,int r){
        if(l==r){
            mi[o]=gcd[o]=a[l];
            num[o]=1;
            return;
        }
        int mid=(l+r)/2;
        build(ls,l,mid);
        build(rs,mid+1,r);
        push_up(o);
    }
    int query(int o,int l,int r,int ql,int qr){
        if(ql<=l&&qr>=r){
            return gcd[o];
        }
        int mid=(l+r)/2;
        int gc=0;
        if(ql<=mid)gc=__gcd(gc,query(ls,l,mid,ql,qr));
        if(qr>mid)gc=__gcd(query(rs,mid+1,r,ql,qr),gc);
        return gc;
    }
}tree;

int sum[maxn*40],rt[maxn*40];
int lss[maxn*40],rss[maxn*40];
int cnt;
void update(int &o,int pre,int l,int r,int val){
    o=++cnt;
    lss[o]=lss[pre];rss[o]=rss[pre];
    sum[o]=sum[pre];
    if(l==r){sum[o]++;return;}
    int mid=(l+r)/2;
    if(val<=mid)update(lss[o],lss[pre],l,mid,val);
    else update(rss[o],rss[pre],mid+1,r,val);
}
int query(int o,int l,int r,int val){
    if(l==r){
        return sum[o];
    }
    int mid=(l+r)/2;
    if(val<=mid)return query(lss[o],l,mid,val);
    else return query(rss[o],mid+1,r,val);
}

int n;

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        update(rt[i],rt[i-1],1,1e9,a[i]);
    }
    tree.build(1,1,n);
    int m;
    cin>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        int gc=tree.query(1,1,n,l,r);
        int num=query(rt[r],1,1e9,gc);
        int num1=query(rt[l-1],1,1e9,gc);
        cout<<r-l+1-num+num1<<endl;

    }
    return 0;
}

Codeforces Round 269 (Div. 2)

Diposting di 2019-04-24 | Edited on 2019-03-27

传送门

C - MUH and House of Cards (数学)

思路

首先每层肯定需要2个作为基础，然后剩下三个作为一个房子

所以我们需要$K$层那就至少需要$n-2k>0$同时剩下的要可以正好摆成房子也就是$(n-2k)mod3==0$

然后我们就判断木棍能否组成一个K层的房子

首先考虑最优的情况，第一层一个第二层两个…所以第一层需要$2$根

第二层需要$2+31$个第三层需要$2+32$个

等差数列求和就是$n>=i(3i+1)/2$

开始想二分写，后面发现$i$是平方的也就是直接枚举暴力就行了

D - MUH and Cube Walls (KMP)

思路

差分一下KMP裸题了，很简单了

Codeforces Round 268 (Div. 2)

Diposting di 2019-04-24 | Edited on 2019-03-26

传送门

C - 24 Game (分类讨论构造)

思路

首先$n<4$肯定无解

然后$n=4$可以用$123*4=24$

$n=5$可以用$1+24+35=24$

发现后面如果多出来的项数$x,x+1$可以变成$x+1-x=1$ 然后乘上上面的$24$相当于没贡献

D - Two Sets (并查集)

思路

对于一个数$x$要么在$A$要么在$B$，如果在$A$并且存在$a-x$那么$a-x$肯定要也在A

在$B$同理，而且不可能出现在两个位置

所以我们创建一个A集合和B集合，如果最后两个集合合体了那就不合法不然就查询在哪个区间

E - Hack it! (构造)

思路

首先考虑一个数字$x$,若$f(x)=y$那么$f(x+1e18)=f(x)+1=y+1$

我们设$\sum_{i=0}^{1e18-1}f(i)=p(moda)$

那么$\sum_{i=1}^{1e18}f(i)=1+\sum_{i=0}^{1e18-1}f(i) =p+1$

同理证明$\sum_{i=2}^{1e18+1}f(i)=p+2$

$\sum_{i=3}^{1e18+2}f(i)=p+3$

直到$\sum_{i=a-p}^{1e18+a-p-1}f(i)=p+a-p=0(mod a)$

所以$l=a-p,r=1e18+a-p-1$

所以需要求出$P$

$P=45x10^{x-1} $x是位数

Codeforces Round 266 (Div. 2)

Diposting di 2019-04-24 | Edited on 2019-03-21

传送门

A - Cheap Travel （暴力枚举）

思路

直接暴力枚举即可

B - Wonder Room (暴力)

思路

暴力判断其中一个值最多判断sqrt（n）

C - Number of Ways （前缀和）

思路

首先答案不是3的倍数就肯定无解

然后就是切两刀的位置

第一刀肯定是1/3的位置

第二道肯定是2/3的位置

然后乘法定理一下

D - Increase Sequence （DP）

思路

想了很久

$dp[ans][num]$ 表示位置在ans并且前面还有k个左端点还没匹配完成

对于

$a[i]+num==h$ 那么就说明前面的num个还没匹配到的左端点都可以满足他

所以他可以选择

do nothing $dp[i][j]+=dp[i-1][j]$

或者画一个右括号 $dp[i][j]+=dp[i-1][j] \times j$ 因为这个右端点可以和左边num个左端点任意匹配

如果$a[i]+num==h-1$ 说明前面num个还没有满足i这个点，那么可以肯定的就是他必须要一个左括号！

所以$dp[i][j]+=dp[i][j-1]$

同时他可以不仅仅画一个左括号，他还可以同时作为一个左端点一个右端点

所以$dp[i][j]+=dp[i][j] \times (j+1)$ $j+1$是因为他不仅可以和左边的$j$个左端点匹配还可以和自己（必须贡献）的左括号匹配

Codeforces Round 264 (Div. 2)

Diposting di 2019-04-24 | Edited on 2019-03-19

传送门

A - Caisa and Sugar （签到）

B - Caisa and Pylons （根据能量守恒定理hhh）

C - Gargari and Bishops （模拟）

题意

给出一个棋盘你可以放两个皇后，皇后可以攻击和他一个对角线的对象。但是两个皇后不能攻击到同一个目标求出皇后攻击目标后获得的最大值

思路

首先对于对角线正对角线的x+y都是固定的，反对角线的X-Y都是固定的

然后我们就枚举对角线的值就行，

通过观察发现不相交的对角线他们的x+y的奇偶不同。所以我们分别求出最大即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e3+50;

ll a[maxn][maxn];
ll maxL[maxn*2];
ll maxR[maxn*2];
int main(){

    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
            maxL[i+j]+=a[i][j];
            maxR[i-j+n]+=a[i][j];
        }
    }
    ll even=0,odd=0,sx,sy,ex,ey;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if((i+j)&1){
                if(maxL[i+j]+maxR[i-j+n]-a[i][j]>=odd){
                    odd=maxL[i+j]+maxR[i-j+n]-a[i][j];
                    sx=i;sy=j;
                }
            }
            else{
                if(maxL[i+j]+maxR[i-j+n]-a[i][j]>=even){
                    even=maxL[i+j]+maxR[i-j+n]-a[i][j];
                    ex=i;ey=j;
                }
            }
        }
    }
    printf("%lld\n",even+odd);
    printf("%lld %lld %lld %lld\n",sx,sy,ex,ey);
    return 0;
}

D - Gargari and Permutations (DP)

题意

求出K个排列的LCS

思路

两种解法：

DP：首先对于第一个排列他们之间的大小关系肯定是固定的，所以我们可以枚举第一个排列的大小关系，判断这个关系在其他k-1个排列中是否也符合如果符合那么后者的答案就可以从前者身上转移而来 $dp[i]=max(dp[i],dp[j]+1)$

dfs：前半部分相同，后面改成每一个符合的关系一起建图。对于每个点求出一个最长路。

//dp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e3+50;
int a[6][maxn];
int id[6][maxn];
int dp[maxn];
int now[maxn];
int k;
bool ok(int u,int v){
    for(int i=2;i<=k;i++){
        if(id[i][u]<id[i][v])return false;
    }
    return true;
}
int main(){
    int n;
    cin>>n>>k;
    for(int j=1;j<=k;j++)
        for(int i=1;i<=n;i++){
            cin>>a[j][i];
            id[j][a[j][i]]=i;
        }
    for(int i=1;i<=n;i++){
        dp[i]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(ok(a[1][i],a[1][j]))dp[a[1][i]]=max(dp[a[1][i]],dp[a[1][j]]+1);
        }
    }
    cout<<*max_element(dp+1,dp+n+1)<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e3+50;
#define bug cout<<"hello"<<endl;
int a[6][maxn];
int id[6][maxn];
int dp[maxn];
int now[maxn];
int k;
bool ok(int u,int v){
    for(int i=1;i<=k;i++){
        if(id[i][u]>id[i][v])return false;
    }
    return true;
}
vector<int>ve[maxn];
int dfs(int u){
    if(dp[u]!=-1)return dp[u];
    int mx=0;
    for(int i=0;i<ve[u].size();i++){
        mx=max(mx,dfs(ve[u][i]));
    }
    return dp[u]=mx+1;
}
int main(){
    int n;
    cin>>n>>k;
    memset(dp,-1,sizeof(dp));
    for(int j=1;j<=k;j++)
        for(int i=1;i<=n;i++){
            cin>>a[j][i];
            id[j][a[j][i]]=i;
        }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if((i!=j)&&ok(i,j)){
                ve[i].push_back(j);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,dfs(i));
    }
    cout<<ans<<endl;
    return 0;

E - Caisa and Tree (暴力/素数筛选)

题意

给你一个树，让你求根（1）到一个点（v）之间路径上和v的值之间GCD不为1的且深度最大的点编号有五十次修改一个点的操作

思路

看到50次修改就已经想到了暴力了。

但是还是想用正常操作做。

初始化每个值的素因子

首先我们对于每个点存一个他的素因子，然后在每次修改的时候重新建图。从根结点开始开一个栈，让遍历到的点进去，判断这个点的素因子是否出现在刚才遍历的路径中。然后选一个最大的。后把当前这个点也入栈。遍历这个点的儿子们。然后回溯的时候把所有的素因子中包括他的弹开。

//讲道理每个素因子开一个vector就可以了。可是一直过不去，其他人用map就过去了。。

第二种暴力解法。对于每个操作离线存起来，然后在修改的时候再把之间的询问一次性遍历。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+50;
#define bug cout<<"hello"<<endl;
int n,q;
int a[maxn];
int prime[maxn];
bool check[maxn];
int cnt;

void init(int N){
    for(int i=2;i<=N;i++){
        if(!check[i]){
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++){
            if(i*prime[j]>N)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
vector<int>ve[maxn];
void gao(int id,int val){
    ve[id].clear();
    for(int i=1;prime[i]*prime[i]<=val&&i<=cnt;i++){
        if(val%prime[i]==0){
            ve[id].push_back(prime[i]);
            while(val%prime[i]==0)val/=prime[i];
        }
    }
    if(val!=1)ve[id].push_back(val);
}
int Laxt[maxn],Next[maxn],To[maxn],res;

void add(int u,int v){
    Next[++res]=Laxt[u];Laxt[u]=res;To[res]=v;
}

int ans[maxn],dep[maxn];
map<int,vector<int> >mp;

void dfs(int u,int fa,int depp){
    ans[u]=-1,dep[u]=depp;
    for(int i=0;i<ve[u].size();i++){
        int v=ve[u][i];
        if(mp[v].size()==0){
            mp[v].push_back(u);
        }
        else{
            if(ans[u]==-1||dep[ans[u]]<dep[mp[v][mp[v].size()-1]])
                ans[u]=mp[v][mp[v].size()-1];
            mp[v].push_back(u);
        }
    }
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(v==fa)continue;
        dfs(v,u,depp+1);
    }
    for(int i=0;i<ve[u].size();i++){
        int v=ve[u][i];
        mp[v].erase(mp[v].end()-1);
    }
}

int main(){
    init(2e6+10);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),gao(i,a[i]);

    for(int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }

    dfs(1,-1,1);
    while(q--){
        int op,x,y;
        scanf("%d",&op);
        if(op==1){
            scanf("%d",&x);
            printf("%d\n",ans[x]);
        }
        else{
            scanf("%d%d",&x,&y);
            a[x]=y;
            gao(x,a[x]);
            dfs(1,-1,1);
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+50;
int Laxt[maxn],Next[maxn<<1],To[maxn<<1],cnt;

void add(int u,int v){
    Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v;
}

int n,q;
int a[maxn];
int ans[maxn];
vector<int>Q[maxn];
vector<int>St;

void dfs(int u,int fa){
    int k=-1;
    if(!Q[u].empty()){
        for(int i=St.size()-1;i>=0;i--){
            int v=St[i];
            if(__gcd(a[u],a[v])!=1){
                k=v;break;
            }
        }
        for(int i=0;i<Q[u].size();i++)ans[Q[u][i]]=k;
        Q[u].clear();
    }
    St.push_back(u);
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(v==fa)continue;
        dfs(v,u);
    }
    St.pop_back();
}

int main(){
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    int res=0;
    for(int i=1;i<=q;i++){
        int op,x,y;
        scanf("%d",&op);
        if(op==1){
            scanf("%d",&x);
            Q[x].push_back(i);
            res++;
        }
        else{
            if(res)dfs(1,-1);
            ans[i]=-10086;
            scanf("%d%d",&x,&y);
            a[x]=y;
            res=0;
        }
    }
    if(res)dfs(1,-1);
    for(int i=1;i<=q;i++)if(ans[i]!=-10086)printf("%d\n",ans[i]);
    return 0;
}

Codeforces Round 262 (Div. 2)

Diposting di 2019-04-24 | Edited on 2019-03-13

传送门

A - Vasya and Socks (签到)

题意

你有n个袜子每天必须穿一个，然后你妈每m天又给你买一个

问你几能连续几天有袜子穿

思路

直接模拟

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int sum=n,k=0;
    while(n>=m){
        n-=m;
        n++;
        sum++;
    }
    printf("%d\n",sum);
    return 0;
}

B - Little Dima and Equation (暴力)

题意

给你一个式子$x=b*s(x)^a+c$ 其中$s(x)$代表x的每一位数的和

给你abc 让你找出所有的x

思路

因为x最多只有1e9所以s(x)最大只有81 所以直接枚举带入看是否正确

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;

vector<ll>ve;
bool check(ll sum,ll i){
    ll ans=0;
    while(sum){
        ans+=sum%10;
        sum/=10;
    }
    return ans==i;
}
int main()
{
    ll a,b,c;
    scanf("%lld%lld%lld",&a,&b,&c);
    for(ll i=1;i<81;i++){
        ll num=i;
        for(int j=1;j<a;j++)num*=i;
        ll sum=b*num+c;
        if(check(sum,i)&&sum>0&&sum<1e9)ve.push_back(sum);
    }
    printf("%d\n",ve.size());
    for(int i=0;i<ve.size();i++)printf("%d ",ve[i]);
    return 0;
}

C - Present （二分+差分）

题意

你种了一排花每个花都有自己的高度，你每天可以给连续的w个花浇水让他们高度+1问你在m天内给花浇水并且得到的花的最矮高度最大

思路

最大最小值就是二分。

枚举答案（高度）然后把低于这个高度的和他以后都浇水，然后判断天数是否足够。

区间加法可以用差分o(1)计算

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;
ll n,m,w;
ll a[maxn];
ll sum[maxn];

bool check(ll mid){
    memset(sum,0,sizeof(sum));
    ll p=m;
    for(int i=1;i<=n;i++){
        sum[i]+=sum[i-1];
        if(sum[i]+a[i]<mid){
            p-=mid-(sum[i]+a[i]);sum[i+w]-=mid-(sum[i]+a[i]);
            sum[i]+=mid-(sum[i]+a[i]);

        }
    }
    return p>=0;
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&w);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    ll l=0,r=1e15,ans=0;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    printf("%lld\n",ans);
    return 0;
}

D - Little Victor and Set (构造)

题意

输入$l,r,k (1\leq l \leq r \leq10^{12};1\leq k \leq min(1e6,r-l+1))$

从[l,r]选至多k个数使得选出的数的异或值最小，输出最小异或值和方案。

思路

分类讨论，首先如果r-l+1<=4，枚举集合解决之。

先面讨论r-l+1>=5的情况：

此时有至少5个数可以选择，故至少有连续的4个数满足2x,2x+1,2x+2,2x+3。

k=1时显然方案为{l}。k==2时，显然方案为{2x,2x+1}。k>=4时，显然方案为{2x,2x+1,2x+2,2x+3}。

k==3时再另外考虑：

首先，异或值至多为1（参考k==2）

我们现在来找异或值可否为0。先假设可以，则显然是选3个数。不妨设x>y>z。

111…1111

111…1110

000…0001

显然x,y,z前半部分必定是如上这样的，但由于我们要使得x,y,z尽量靠近，所以x,y,z前半部分必然是如下

之后，每添加一位，有可能是yi=zi=1,xi=0或xi=zi=1,yi=0或xi=yi=1,zi=0。

由于要x,y,z尽量靠近，所以显然采取yi=zi=1,zi=0。

所以x,y,z的二进制形式如下

110…0

101…1

011…1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e6+50;
const ll inf=1e17;
typedef unsigned long long ull;
int cnt(int i){
    int ans=0;
    while(i)i-=i&(-i),ans++;
    return ans;
}
int main()
{
    ll l,r,k;
    scanf("%lld%lld%lld",&l,&r,&k);
    if(r-l+1<5){
        int n=r-l+1;
        ll ans=inf;
        vector<ll>val;
        for(int i=1;i<(1<<n);i++){
            ll x=0;
            for(int j=0;j<n;j++)
                if(i&(1<<j))x^=(l+j);
            if(x<ans&&cnt(i)<=k){
                ans=x;
                val.clear();
                for(int j=0;j<n;j++)if(i&(1<<j))val.push_back(l+j);
            }
        }
        cout<<ans<<endl;
        cout<<val.size()<<endl;
        for(int i=0;i<val.size();i++)cout<<val[i]<<" ";
    }
    else{
        if(k==1)cout<<l<<endl<<1<<endl<<l<<endl,exit(0);
        if(k==2){
            if(l&1)l++;
            cout<<1<<endl<<2<<endl<<l<<" "<<l+1<<endl;
            exit(0);
        }
        if(k>=4){
            if(l&1)l++;
            cout<<0<<endl<<4<<endl;
            for(int i=0;i<4;i++)cout<<l+i<<" ";
        }
        else{
            ll x=-1,y,z;
            for(ll i=3;i<=r;i<<=1){
                if((i^(i-1))>=l){
                    x=i;
                    y=i-1;
                    z=i^(i-1);break;
                }
            }
            if(x==-1){
                if(l&1)l++;
                cout<<1<<endl<<2<<endl<<l<<" "<<l+1<<endl;
                exit(0);
            }
            else{
                cout<<"0"<<endl;
                cout<<3<<endl;
                cout<<x<<" "<<y<<" "<<z<<endl;
            }
        }
    }
    return 0;
}

E - Roland and Rose (几何+暴力)

题意

让你在距离圆心$r$的距离中选n个整点使得这$n$个点的两两欧几里得距离平方和最大

思路

直接枚举距离圆心最远的点然后暴力判断…不会证明。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e6+50;
const ll inf=1e17;
typedef unsigned long long ull;
struct Point{
    int x,y;
};
int N,R,M,ans;
vector<Point>vec;
vector<int>anw,now;
int dis(int x,int y){
    return x*x+y*y;
}
bool cmp(Point a,Point b){
    return dis(a.x,a.y)>dis(b.x,b.y);
}
void dfs(int cnt,int in,int value){
    if(cnt==N){
        if(value>ans){
            ans=value;
            anw=now;
        }
        return;
    }
    for(int i=in;i<M;i++){
        int res=0;
        for(int j=0;j<cnt;j++)
            res+=dis(vec[now[j]].x-vec[i].x,vec[now[j]].y-vec[i].y);
        now.push_back(i);
        dfs(cnt+1,i,value+res);
        now.pop_back();
    }
}
int main()
{
    scanf("%d%d",&N,&R);
    for(int i=-R;i<=R;i++){
        for(int j=-R;j<=R;j++){
            if(i*i+j*j<=R*R)
            vec.push_back(Point{i,j});
        }
    }
    ans=0;
    M=min((int)vec.size(),18);
    sort(vec.begin(),vec.end(),cmp);
    dfs(0,0,0);
    printf("%d\n",ans);
    for(int i=0;i<N;i++)
        printf("%d %d\n",vec[anw[i]].x,vec[anw[i]].y);
    return 0;
}

Codeforces Round 256 (Div. 2)

Diposting di 2019-04-24 | Edited on 2019-03-02

传送门

A.A - Rewards (签到)

题意

三种A物品，三种B物品；

容器一次只能装五个A或者十个B不能同时装A和B

思路

水

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+9;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int a=0,b=0;
    for(int i=1;i<=3;i++){
        int aa;cin>>aa;
        a+=aa;
    }
    for(int i=1;i<=3;i++){
        int aa;cin>>aa;
        b+=aa;
    }
    int n;cin>>n;
    int num1=a/5+(a%5?1:0);
    int num2=b/10+(b%10?1:0);
    cout<<(num1+num2<=n?"YES":"NO");
    return 0;
}

B - Suffix Structures (分类讨论)

题意

让你判断字符串A能否变成字符串B

如果字符串A能通过删去某些数变成B 输出巴拉巴拉

如果字符串A能通过对调某个数变成B 输出巴拉巴拉

如果字符串A同时需要上面两个操作才能变成B 输出巴拉巴拉

如果字符串A通过上面两个操作都不能变B 输出巴拉巴拉

思路

还有啥，直接模拟呗

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+9;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
string s,t;
int a[maxn];
int b[maxn];
bool find(){
    int pos=0;
    for(int i=0;i<t.size();i++){
        bool ok=false;
        int j;
        for(j=pos;j<s.size();j++){
            if(s[j]==t[i]){ok=true;break;}
        }
        if(!ok)return false;
        else pos=j+1;
    }
    return true;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>s>>t;
    int len1=s.size(),len2=t.size();
    for(int i=0;i<len1;i++){
        a[s[i]-'a']++;
    }
    for(int i=0;i<len2;i++){
        b[t[i]-'a']++;
    }
    int flag=0;
    for(int i=0;i<26;i++){
        if(a[i]==b[i])continue;
        if(a[i]<b[i])cout<<"need tree",exit(0);
        else{
            flag=1;
        }
    }
    if(!flag){
        puts("array");return 0;
    }
    if(flag){
        if(find())
            puts("automaton"),exit(0);
        else{
            puts("both");return 0;
        }
    }
    return 0;
}

C - Painting Fence（分治）

题意

给出一排木板，木板的高度为A[i]，宽度为1.

你手里有一个大小为1的刷子，你每次可以一次性刷一条不间断直线

问你最少刷几次可以把这一排木板刷完

思路

首先假设如果我们全部横着刷

那么我们就需要最爱的木板高度+其他凸出来的次数

假设我们数着刷那么我们就需要刷木板的个数

所以我们就只要这两种情况取个优

再判断横着刷的时候凸出来的需要另外考虑这又是一个小问题，所以我们可以分治去做

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+9;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n;
ll a[maxn];
ll dfs(int s,int t){
    if(s>t)return 0;
    ll mi=inf,need=0;
    for(int i=s;i<=t;i++){
        mi=min(a[i],mi);
    }
    need+=mi;
    for(int i=s;i<=t;i++)
        a[i]-=mi;
    int st=s;
    for(int i=st;i<=t;i++)
        if(i==t&&a[i])
            need+=dfs(st,i),st=i+1;
        else if(!a[i])
            need+=dfs(st,i-1),st=i+1;
    return min(1LL*(t-s+1LL),need);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cout<<dfs(1,n);
    return 0;
}

D.D - Multiplication Table （二分）

题意

对于一个乘法表求出第K大的数是多少

思路

我们发现对于一行或者一列他们的值都是递增的所以满足二分的性质

于是我们二分答案；

可以求出每一行有多少个值小于这个答案

include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+9;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll n,m,k;cin>>n>>m>>k;
    ll l=0,r=n*m,ans=-1;
    while(l<=r){
        ll mid=(l+r)/2;
        ll sum=0;
        for(int i=1;i<=n;i++)
            sum+=min(m,(mid-1)/i);
        if(sum<k){
            l=mid+1;
            ans=mid;
        }
        else
            r=mid-1;
    }
    cout<<ans;
    return 0;
}

E - Divisors (dfs)

题意

定义一个函数为F（a）{a为一个数组}

F（a)的值为a的元素的所有因数依次排列

定义一个数组P[a]

P[i]的递推式为P[i]=P(X[i-1])

现在给你P[0]让你求出P[k];

思路

很明显这个P是递归的，而且只需要输出前1e5项，那么我们就直接暴力枚举因子就行

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
vector<ll>ve;
int len;
ll num;
void dfs(ll n,ll k){
    if(num>=1e5)return;
    if(k==0||n==1){
        num++;
        cout<<n<<" ";
        return ;
    }
    for(ll i=0;i<ve.size()&&ve[i]<=n;i++)
        if(n%ve[i]==0)dfs(ve[i],k-1);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll x,k;
    cin>>x>>k;
    for(ll i=1;i*i<=x;i++){
        if(x%i==0){
            ve.push_back(i);
            if(i*i!=x)ve.push_back(x/i);
        }
    }
    sort(ve.begin(),ve.end());
    len=ve.size();
    dfs(x,k);
    return 0;
}

Codeforces Round 251 (Div. 2)

Diposting di 2019-04-24 | Edited on 2019-02-24

传送门

A.[Devu, the Singer and Churu, the Joker (签到)

题意

主角有N首不同时长的歌曲，每首歌曲之间需要相隔10分钟,并且歌曲必须连续，再主角唱完歌的时候可以表演每次五分钟的其他节目。问最多表演多少场其他节目，不能完成演唱输出-1

思路

直接先按照题意安排歌曲，然后再在空缺的时间中填充魔术。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int a[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,d;
    cin>>n>>d;
    for(int i=1;i<=n;i++)cin>>a[i];
    if((n-1)*10>=d){
        cout<<-1<<endl;return 0;
    }
    int cnt=0;
    int ex=d-(n-1)*10;
    int num=0;
    for(int i=1;i<=n;i++){
        if(i!=1)num+=10,cnt+=2;
        num+=a[i];
    }
    if(num>d){
        cout<<-1<<endl;return 0;
    }
    else{
        cnt+=(d-num)/5;
        cout<<cnt<<endl;
    }
    return 0;
}

B.Devu, the Dumb Guy (贪心)

题意

n个课程，每个课程都有ci个章节，完成一章需要X分钟，但是如果完成一个课程后面的课程每章都会减少一分钟（最少不低于1分钟），问少需要几分完成所有课程。

题解

直接排序然后根据题意模拟贪心。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int a[maxn];
int cnt[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,x;
    cin>>n>>x;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    ll sum=0;
    for(int i=1;i<=n;i++){
        sum+=a[i]*max(1LL*(x-i+1LL),1LL);
    }
    cout<<sum<<endl;
    return 0;
}

C.Devu and Partitioning of the Array （大模拟）

题意

给出N个数，让你分成k块，其中p块的和为偶数

思路

只要知道偶数+偶数=偶数，奇数+奇数=偶数奇数+偶数=奇数的特性就可以做了，

不过情况比较多需要讨论

先把奇数偶数分类，然后如果奇数比较多，就判断奇数多出来的那些可不可以组成偶数（也就是多出来的是不是偶数个）

注意讨论奇数和偶数分别为0的情况。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll a[maxn];
stack<int>odd,even,exeven,exodd;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,k,p;
    cin>>n>>k>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]&1)odd.push(a[i]);
        else even.push(a[i]);
    }
    int oddnum=odd.size();
    int odd_need_num=k-p;
    int even_need_num=p;
    if(odd_need_num>oddnum){
        cout<<"NO"<<endl;return 0;
    }
    else{
        if((oddnum-odd_need_num)%2!=0){
            cout<<"NO"<<endl;return 0;
        }
        else{
            int ex=oddnum-odd_need_num;
            for(int i=1;p!=0&&i<=ex;i++){
                exeven.push(odd.top());
                odd.pop();
            }
            if(!p){
                while(!even.empty()){
                    exodd.push(even.top());
                    even.pop();
                }
            }
            if(ex/2+even.size()<even_need_num){
                cout<<"NO"<<endl;return 0;
            }
            cout<<"YES"<<endl;
            for(int i=1;i<odd_need_num;i++){
                cout<<1<<" "<<odd.top()<<endl;
                odd.pop();
            }
            if(!odd.empty()){
                cout<<odd.size()+exodd.size()<<" ";
                while(!odd.empty()){
                    cout<<odd.top()<<" ";
                    odd.pop();
                }
                while(!exodd.empty()){
                    cout<<exodd.top()<<" ";
                    exodd.pop();
                }
                cout<<endl;
            }
            for(int i=1;i<p;i++){
                if(!even.empty()){
                    cout<<1<<" "<<even.top()<<endl;
                    even.pop();
                }
                else{
                    cout<<2<<" "<<exeven.top();
                    exeven.pop();
                    cout<<" "<<exeven.top()<<endl;
                    exeven.pop();
                }
            }
            if(even.size()+exeven.size()==0)return 0;
            cout<<even.size()+exeven.size()<<" ";
            while(!even.empty()||!exeven.empty()){
                if(!even.empty()){
                    cout<<even.top()<<" ";
                    even.pop();
                }
                else{
                    cout<<exeven.top()<<" ";
                    exeven.pop();
                    cout<<exeven.top()<<" ";
                    exeven.pop();
                }
            }
        }
    }
    return 0;
}

D.Devu and his Brother (三分)

题意

两个数组A,B.想要数组A的最小值不比数组B的最大值小,一次操作可以让某个数字的一个元素增大或者减小1 问达成目的最少需要几次操作。

思路

题目的意思就是找出一个值X使得A中的所有元素都大于等于X，B中的元素小于等于X。

所以答案就是

$ans=(\sum_{i=1}^{n}x-a[i])+(\sum_{i=1}^{m}b[i]-x)\\a[i]<x,b[i]>x$

假设这个x是最优的解，那么X增大或者减小都会使得ans变大，所以题目就是一个凹函数求最小值了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll a[maxn];
ll b[maxn];
int n,m;
ll check(ll x){
    ll ans=0;
    for(int i=1;i<=n;i++)if(a[i]<x)ans+=x-a[i];
    for(int i=1;i<=m;i++)if(b[i]>x)ans+=b[i]-x;
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    for(int i = 1; i <= m; i++){
        cin>>b[i];
    }
    ll l=0,r=1e11,ans=inf;
    for(int i=1;i<=100;i++){
        ll m1=(l+r)/2;
        ll m2=(m1+r)/2;
        ll ans1=check(m1),ans2=check(m2);
        if(ans1>ans2){
            l=m1;
            ans=min(ans,ans2);
        }
        else{
            r=m2;
            ans=min(ans,ans1);
        }
    }
    cout<<ans<<endl;
    return 0;
}

E.Devu and Birthday Celebration （莫比乌斯反演，素因子分解,计数原理,组合数学）

题意

Q次询问给出一个数N 让你分成F份，使得这F份的和为N并且这F份数最大公约数为1，问有多少种分法。Q,N,F范围都是1-1e5。

思路

如果不考虑公约数那么答案就是Cn-1,f-1。

设F(n,k)为n个数分成F份并且最大公约数为1的答案数

所以

$F(n,k)=C_{n-1}^{k-1}-\sum_{g>1}^{n}F(n/g,k)$

然后直接递归写就行。

$F(n)=n分解为k份最大公约数为任意的值$ $G(n)=n分解为k份且最大公约数为n的值$

可知

$F(n,k)=C_{n-1}^{k-1}$

同时

$F(n)=\sum_{d|n}G(d)$

于是根据莫比乌斯反演因数反演

$G(n)=\sum_{d|n}u(d)F(n/d)$

/*
    莫比乌斯反演
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll inv[maxn],p[maxn];
ll ksm(ll x,ll n){
    ll ans=1;
    while(n){
        if(n&1)ans=(ans*x)%mod;
        x=(x*x)%mod;
        n>>=1;
    }
    return ans;
}
int prime[maxn];
bool notprime[maxn];
int mu[maxn];
void init(int n){
    mu[1]=1;
    int tot=0;
    for(int i=2;i<=n;i++){
        if(!notprime[i])prime[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot;j++){
            if(i*prime[j]>n)break;
            notprime[i*prime[j]]=true;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }
            else mu[i*prime[j]]=-mu[i];
        }
    }
    inv[0]=p[0]=1;
    for(int i=1;i<=n;i++)
        p[i]=p[i-1]*i%mod,inv[i]=ksm(p[i],mod-2);
}
ll cal(int n,int m){
    if(n<m)return 0LL;
    return p[n]*inv[n-m]%mod*inv[m]%mod;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    init(1e5);
    int q;
    cin>>q;
    while(q--){
        ll n,f;
        cin>>n>>f;
        ll ans=0;
        for(int i=1;i*i<=n;i++){
            if(n%i==0){
                ans=(ans+mu[i]*cal(n/i-1,f-1)+mod)%mod;
                if(n/i!=i)ans=(ans+mu[n/i]*cal(i-1,f-1)+mod)%mod;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

/*
	枚举GCD值
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll inv[maxn],p[maxn];
ll ksm(ll x,ll n){
    ll ans=1;
    while(n){
        if(n&1)ans=(ans*x)%mod;
        x=(x*x)%mod;
        n>>=1;
    }
    return ans;
}
vector<int>G[maxn];
void init(int n){
    inv[0]=p[0]=1;
    for(int i=1;i<=n;i++)
        p[i]=p[i-1]*i%mod,inv[i]=ksm(p[i],mod-2);
    for(int i=2;i<=n;i++){
        for(int j=i;j<=n;j+=i){
            G[j].push_back(i);
        }
    }
}
ll cal(int n,int m){
    if(n<m)return 0LL;
    return p[n]*inv[n-m]%mod*inv[m]%mod;
}
ll vis[maxn];
int who[maxn];
ll F(int n,int k,int q){
    if(who[n]==q)return vis[n];
    ll ans=cal(n-1,k-1);
    for(int i=0;i<G[n].size();i++){
        ans=(ans-F(n/G[n][i],k,q)+mod)%mod;
    }
    who[n]=q;
    vis[n]=ans;
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    init(1e5);
    int q;
    cin>>q;
    while(q){
        ll n,f;
        cin>>n>>f;
        cout<<F(n,f,q)<<endl;
        q--;
    }
    return 0;
}

/*
	枚举GCD倍数
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll inv[maxn],p[maxn];
ll ksm(ll x,ll n){
    ll ans=1;
    while(n){
        if(n&1)ans=(ans*x)%mod;
        x=(x*x)%mod;
        n>>=1;
    }
    return ans;
}
void init(int n){
    inv[0]=p[0]=1;
    for(int i=1;i<=n;i++)
        p[i]=p[i-1]*i%mod,inv[i]=ksm(p[i],mod-2);
}
ll cal(int n,int m){
    if(n<m)return 0LL;
    return p[n]*inv[n-m]%mod*inv[m]%mod;
}
vector<int> get(int n){
    vector<int>G;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            G.push_back(i);
            while(n%i==0)n/=i;
        }
    }
    if(n!=1)G.push_back(n);
    return G;
}
ll F(int n,int k){
    vector<int>G=get(n);
    ll ans=0,num=1<<G.size();
    for(int i=0;i<num;i++){
        ll tmp=1,sign=1;
        for(int j=0;j<G.size();j++){
            if(i&(1<<j)){
                sign*=-1;
                tmp*=G[j];
            }
        }
        ans=(ans+sign*cal(n/tmp-1,k-1)%mod+mod)%mod;
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    init(1e5);
    int q;
    cin>>q;
    while(q--){
        ll n,f;
        cin>>n>>f;
        cout<<F(n,f)<<endl;
    }
    return 0;
}

luowentaoaa

嘤嘤嘤

125 posting

53 tags

A. Ehab and another construction problem(水题，暴力)

题解

B.Ehab and subtraction (排序，优先队列)

C.Ehab and a 2-operation task (思维)

题意

题解

D.Ehab and another another xor problem (思维,位运算)

题意

题解

E.Ehab and a component choosing problem (树形DP，贪心)

题意

题解

思路

思路

D - Dreamoon and Sets (找规律)

思路

E - Dreamoon and String (Dp)

思路

C.Captain Marmot (几何,点旋转)

思路

Flowers (DP)

思路

E - Pillars (DP+线段树+离散化)

思路

F - Ant colony (线段树区间gcd,线段树求最小值的个数)

思路

C - MUH and House of Cards (数学)

思路

D - MUH and Cube Walls (KMP)

思路

C - 24 Game (分类讨论 构造)

思路

D - Two Sets (并查集)

思路

E - Hack it! (构造)

思路

A - Cheap Travel （暴力枚举）

思路

B - Wonder Room (暴力)

思路

C - Number of Ways （前缀和）

思路

D - Increase Sequence （DP）

思路

A - Caisa and Sugar （签到）

B - Caisa and Pylons （根据能量守恒定理hhh）

C - Gargari and Bishops （模拟）

题意

思路

D - Gargari and Permutations (DP)

题意

思路

E - Caisa and Tree (暴力/素数筛选)

题意

思路

A - Vasya and Socks (签到)

题意

思路

B - Little Dima and Equation (暴力)

题意

思路

C - Present （二分+差分）

题意

思路

D - Little Victor and Set (构造)

题意

思路

E - Roland and Rose (几何+暴力)

题意

思路

A.A - Rewards (签到)

题意

思路

B - Suffix Structures (分类讨论)

题意

思路

C - Painting Fence（分治）

题意

思路

D.D - Multiplication Table （二分）

C - 24 Game (分类讨论构造)