G ( X , Y ) = X 的因子 Y 个数 G(X,Y) = X的因子Y个数 G(X,Y)=X的因子Y个数
例如 G ( 8 , 2 ) = 3 G(8,2)=3 G(8,2)=3
G ( 12 , 2 ) = 2 G(12,2)=2 G(12,2)=2
F ( X , Y ) = ∑ i = 1 X G ( i ) F(X, Y) = \sum_{i=1}^{X} G(i) F(X,Y)=i=1∑XG(i)
直接上结论
F ( X , Y ) = X Y 1 + ⋯ + X Y i = ∑ i = 1 k X Y i F(X,Y)= \frac{X}{Y^1} + \cdots + \frac{X}{Y^i} = \sum_{i=1}^{k} \frac{X}{Y^i} F(X,Y)=Y1X+⋯+YiX=i=1∑kYiX
其中 k k k为 Y k < = X Y^k<= X Yk<=X, k k k的最大值
ll cnt(ll x, int y){if(x < 1){return 0;}ll count = 0;while(x >= y){x /= y;count += x;}return count;
}