【打表+数学】CF729div2 C. Strange Function

亦凉 2024-03-22 14:03 54阅读 0赞

**规律找出来了，但是不会统计贡献....**

**1600太难了我跳**

题意：

![8c24935440cd46eba43e83d6ea0c96b0.png][]

![a8785c90a73e444d9de5ad4e5ee4e3ea.png][]

思路：

看数据范围就是O(1)计算贡献

所以考虑打表，还真被我打出来了：

> 1 : 2  
> 2 : 3  
> 3 : 2  
> 4 : 3  
> 5 : 2  
> 6 : 4  
> 7 : 2  
> 8 : 3  
> 9 : 2  
> 10 : 3  
> 11 : 2  
> 12 : 5  
> 13 : 2  
> 14 : 3  
> 15 : 2  
> 16 : 3  
> 17 : 2  
> 18 : 4  
> 19 : 2  
> 20 : 3

规律一目了然，但是我不会算贡献....

对于每一个x，其贡献最少为2

而第一个出现3的位置是2，第一个出现4的位置是6，第一个出现5的地方是12，由此可见，第一次出现x的位置是1~x-1的最小公倍数

然后就可以开始猜了，首先明确每个i的贡献最少为2，然后对于2的倍数，那么2就不可取，贡献加1，对于6的倍数，3不可取，贡献再加1，对于12的倍数，4不可取，贡献再加1，以此类推……

于是我们可以先打表，对于k:143，求出1k-1的最小公倍数，如果数x想要有calc\[k\]的贡献，那么它一定是calc\[k\]的倍数，我们可以通过x/calc\[k\]得到x中包含calc\[k\]的倍数的个数，其个数便是在原有基础上再+1的贡献值，最后相加即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mod=1e9+7;
    
    int N,ans;
    int a[mxn];
    
    void db(int x){
    	int res=0;
    	for(int j=1;j<=x;j++){
    		if(x%j!=0){
    			res=j;
    			break;
    		}
    	}
    	if(x==1) res=2;
    	else if(x==2) res=3;
    	cout<<x<<" : "<<res<<'\n';
    }
    void init(){
    	a[1]=a[2]=2;
    	for(int i=3;i<=42;i++) a[i]=a[i-1]*(i-1)/__gcd(i-1,a[i-1]);
    }
    void solve(){
    	/*for(int x=1;x<=50;x++){
    		db(x);
    	}*/
    	cin>>N;
    	int ans=N*2;
    	for(int i=3;i<=42;i++) ans=(ans+(N/a[i]+mod))%mod;
    	cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;cin>>__;
    	init();
        while(__--)solve();return 0;
    }

[8c24935440cd46eba43e83d6ea0c96b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/869683b3253540938656ed49450cdc58.png
[a8785c90a73e444d9de5ad4e5ee4e3ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/b8234f878cb44012984f993337c906c5.png