C. Strange Function (思维+数论)

墨蓝 2022-09-13 06:19 163阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZCN5a2X5LiN6IO955u45ZCM_size_20_color_FFFFFF_t_70_g_se_x_16]  
 1   2   3   . . .   x − 1 1 \\ 2 \\ 3 \\ ... \\ x-1 1 2 3 ... x−1 是  i i i 的因子，  x x x 不是  i i i 的因子

容易得出 l c m ( 1 , 2 , . . . , x − 1 ) lcm(1, 2, ...,x-1) lcm(1,2,...,x−1) 是  i i i 的因子，但 l c m ( 1 , 2 , 3... , x − 1 , x ) lcm(1, 2, 3...,x-1, x) lcm(1,2,3...,x−1,x) 不是  i i i 的因子

对于  i i i 贡献的数，这些数的因子包含 1 , 2 , … , i − 1 1,2,…,i-1 1,2,…,i−1的最小公倍数且不包含  i i i 这个因子，因子包含 1 , 2 , … , i − 1 1,2,…,i-1 1,2,…,i−1的最小公倍数的数的个数为 n / l c m ( 1 , 2 , … , i − 1 ) n/lcm(1,2,…,i-1) n/lcm(1,2,…,i−1)，这些数中部包含因子i的个数为 n / l c m ( 1 , 2 , … , i ) n/lcm(1,2,…,i) n/lcm(1,2,…,i)

通过简单的容斥， i i i 的贡献为上述两数之差再乘以  i i i 即可。

[题解来源][Link 1]

const int mod = 1e9 + 7;
    ll a[50];
    ll gcd(ll a, ll b){ return b ? gcd(b,a%b):a;}
    
    void solve()
    { 
    	ll n;
    	cin >> n;
    	
    	a[1] = 1;
    	for(int i=2;;i++)
    	{ 
    		a[i] = a[i-1] * i / gcd(a[i-1],i);
    		if(a[i] > 1e16+100) break;
    	}
    	
    	ll res = 0;
    	
    	for(int i=2;;i++)
    	{ 
    		ll x = n/a[i-1], y = n/a[i];
    		
    		res = (res + i*(x-y))%mod;
    		
    		if(!y) break;
    	}
    	
    	cout << res << endl;
    
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZCN5a2X5LiN6IO955u45ZCM_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/89c74a50fcfb454880e97f66873eab2c.png
[Link 1]: https://blog.csdn.net/yezi_coder/article/details/118640937?utm_medium=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromBaidu~default-3.no_search_link&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromBaidu~default-3.no_search_link